【校招VIP】前端算法考察之动态规划- 校招VIP

考点介绍：

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

本期分享的内容分为试题、文章以及视频三部分。

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

一、考点题目

1、8*8的棋盘的每个小格里放着一个价值互不相同的礼物，一个人初始位置在左上角，每次只能向下或者向右走一步，并获得相应位置的礼物，结束位置在棋盘的右下角，设计一个算法能够使得到的礼物的总价值最大

解答：考虑中间状态，设D[i][j]为棋盘位置(i,j)时，可以获得的最大价值; val[i][j]为（i, j）位置礼物的价值......

2、下面哪个不是动态规划算法的基本要素（）

A.子问题重叠性

B.建立表格不断填表

C.马尔可夫性

D.最优子结构

正确答案：C，动态规划，利用问题的最优子结构性质，以自底向上的方式递归的从子问题的最优解逐步构造出整个问题的最优解.....

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

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

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

解答：运用的是动态规划的思想，由于是求最长回文字符串。dp数组定义为：在子串s[i…j]中，最长回文子序列的长度为dp[i][j]......

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

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

二、考点文章

1、动态规划算法

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

2、JavaScript算法之动态规划

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

3、动态规划的简单理解及例子

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

三、考点视频

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

前端是IT校招中目前性价比最高的职位，对所学专业要求不高，考点难度较小，且需求量大。校招时分为一二线公司和普通公司，所对应的校招要求、工资和职业发展都是有差别的……