递归和动态规划 about blog HOT 2 OPEN

动态规划其实是分治策略的一个子集，即将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。 关键点就在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解多次，解决思路是将已求解的子问题的解存储起来，当下次再次求解这个子问题时，直接套用即可。

分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。

动态规划概念的关键点：

• 动态规划法只会解决每个子问题一次
• 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查用

继续以上爬台阶问题，从 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 的空间。

关于时间空间复杂度

from blog.

TODOS:

• 树形DP：01背包问题
• 线性DP：最长公共子序列、最长公共子串
• 区间DP：矩阵最大值（和以及积）
• 数位DP：数字游戏
• 状态压缩DP：旅行商

from blog.