考点介绍：

动态规划算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。动态规划可以通过填表的方式来逐步推进，得到最优解。

本期分享的前端算法考点之动态规划，分为试题、文章以及视频三部分。

答案详情解析和文章内容可扫下方二维码或链接即可查看！

一、考点题目

1、某一问题可用动态规划算法求解的显著特征是？

解答：该问题具有最优子结构性质……

2、最优二叉搜索树问题的动态规划算法（设函数名 binarysearchtree）

解答：

void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w)
 
{
 
int i,j,k,t,l;
 
for(i=1;i<=n+1;i++)
 
{
 
w[i][i-1]=a[i-1];
 
m[i][i-1]=0;
 
}
 
for(l=0;l<=n-1;l++)//----l 是下标 j-i 的差
 
for(i=1;i<=n-l;i++)
 
{
 
j=i+l;
 
w[i][j]=w[i][j-1]+a[j]+b[j];
 
m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];
 
s[i][j]=i;
 
for(k=i+1;k<=j;k++)
 
{
 
t=m[i][k-1]+m[k+1][j]+w[i][j];
 
if(t<m[i][j])
 
{
 
m[i][j]=t;
 
s[i][j]=k;
 
}
 
}
 
}
 
}

3、简述分治法和动态规划算法的联系和区别。

解答：分治和动态规划共同点：两者都是把大问题转换成小问题/子问题来解决，并且当最优子问题组合成最优大问题，关键点在于找到子问题的划分......

（答案点击下方链接或者扫海报二维码查看哦）

二、考点文章

1、JavaScript算法之动态规划

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。……

2、动态规划算法

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。动态规划算法与分治算法类似。其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解……

（扫下方海报二维码查看完整版）

三、考点视频

1、动态规划之下楼梯的步数方案

动态规则是算法的一种类型，包括转移函数、结束逻辑等，是开发岗校招笔试和面试的大头，必须要掌握……

更多资讯可搜索校招VIP小程序查看哦！
移动端链接：https://m.xiaozhao.vip/dTopic/detail/450
PC端链接：https://xiaozhao.vip/dTopic/detail/450