JTangming
commented
4 years ago 动态规划其实是分治策略的一个子集，即将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。 关键点就在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解多次，解决思路是将已求解的子问题的解存储起来，当下次再次求解这个子问题时，直接套用即可。
分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。
动态规划概念的关键点：
- 动态规划法只会解决每个子问题一次
- 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查用
继续以上爬台阶问题，从 f(n)->...->f(n-k)+f(n-k-1)->...->f(2) + F(1)，会存在重复计算 f(n-k)、f(n-k-1) 的问题。
用动态规划的思路，可以将问题解决办法倒转一下，即从递归出口向上推导：
第一次迭代，如果台阶数为 3 ，那么走法数为 3 ，通过 f(3) = f(2) + f(1) 得来。
第二次迭代，如果台阶数为 4 ，那么走法数为 5 ，通过 f(4) = f(3) + f(2) 得来。
// 第 n-k 次 ...
由此可见，每一次迭代过程中，只需要保留之前的两个状态，就可以推到出新的状态。翻译成代码如下：
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
const dp = [];
dp[1] = 1;
dp[2] = 2;
for(let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};复杂度分析： 时间复杂度：O(n)，单循环到 n 空间复杂度：O(n)，dp 数组用了 n 的空间。
递归算法是一种直接或者间接调用自身函数或者方法的算法。 递归算法的实质是把问题分解成小规模的同类问题，这些同类问题作为子问题递归调用来表示问题的解。特点如下：
下面通过爬台阶问题来理解一下递归算法，问题描述：一个人爬楼梯，每次只能爬1个或2个台阶，假设有n个台阶，那么这个人有多少种不同的爬楼梯方法？
套用以上的递归特点，思考如下：【问题拆分】可以根据第一步的走法把所有走法分为两类：
所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 ，然后加上先走 2 阶后，n-2 个台阶的走法。
用公式表示就是：
有了递推公式，递归代码基本上就完成了一半。那么接下来考虑【递归终止条件】。
从以上公式得知，最终出口是f(2)、f(1)。当有一个台阶时，我们不需要再继续递归，就只有一种走法，即 f(1)=1。f(2) 表示走 2 个台阶，有两种走法，一步走完或者分两步来走，即 f(2)=2。
总结以上思路，递归条件基本如下：
翻译成代码如下：