考点介绍：

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

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

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

一、考点题目

1、最优二叉搜索树问题的动态规划算法（设函数名 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;
 
}
 
}
 
}
 
}

2、给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

解答：运用的是动态规划的思想，由于是求最长回文字符串......

3、(120三角形最小路径和) 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

解答：相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点......

4、小区成二叉树结构，如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

解答：选择二叉树中不相邻的节点，使得节点之和为最大......

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

二、考点文章

1、动态规划算法

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法……

2、JavaScript算法之动态规划

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程……

3、【校招VIP】动态规划的简单理解及例子

动态规划是分治的延伸，通俗一点来说就是大事化小，小事化无的艺术，在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果……

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

三、考点视频

1、前端校招的特点、考点和职业发展

前端是IT校招中目前性价比最高的职位，对所学专业要求不高，考点难度较小，且需求量大……

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