递归和动态规划

[JTangming]

递归算法是一种直接或者间接调用自身函数或者方法的算法。
递归算法的实质是把问题分解成小规模的同类问题，这些同类问题作为子问题递归调用来表示问题的解。特点如下：

• 一个问题的解可以分解为几个子问题的解
• 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
• 存在递归终止条件，即存在递归出口

下面通过爬台阶问题来理解一下递归算法，问题描述：一个人爬楼梯，每次只能爬1个或2个台阶，假设有n个台阶，那么这个人有多少种不同的爬楼梯方法？

套用以上的递归特点，思考如下：【问题拆分】可以根据第一步的走法把所有走法分为两类：

• 第一类是第一步走了 1 个台阶
• 第二类是第一步走了 2 个台阶

所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 ，然后加上先走 2 阶后，n-2 个台阶的走法。

用公式表示就是：

f(n) = f(n-1)+f(n-2)

有了递推公式，递归代码基本上就完成了一半。那么接下来考虑【递归终止条件】。

从以上公式得知，最终出口是f(2)、f(1)。当有一个台阶时，我们不需要再继续递归，就只有一种走法，即 f(1)=1。f(2) 表示走 2 个台阶，有两种走法，一步走完或者分两步来走，即 f(2)=2。

总结以上思路，递归条件基本如下：

f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)

翻译成代码如下：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
};

[JTangming]

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

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

动态规划概念的关键点：

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

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

关于时间空间复杂度

[JTangming]

TODOS:

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