递推算法与递推套路（手撕算法篇）

联系我们：有道技术团队助手：ydtech01 / 邮箱：[[email protected]]

之前学习基础知识的时候也说了，递推和动态规划有这暧昧不清的关系，可以说，动态规划就是多了一个决策过程的递推。因此，我们今天的刷题也会涉及到一些比较简单的动态规划的题目，同样能够对我们深刻的理解递推算法起到帮助，也为我们之后深入学习动态规划算法和动态规划的优化打下基础。

一、前置知识

每一个递推算法，都有一个递推公式，通过递推公式我们可以更加明确的了解递推算法。

1.1 斐波那契数列的递推公式

使用场景：当我们下（上）一行的状态可以仅仅通过上（下）一行的信息推导出来，并要求我们求解最后（第）一行时，我们无需将每一行的数据都存储在数组当中，可以通过滚动数组的技巧，节省空间复杂度。

具体实现：假设我们已经知道第一行的数据，并且通过第一行数据经过一定的运算可以得到第二行的数据，那么，我们只需要一个数组临时存储两行数据，就可以将之后的每一行数据的结果计算出来，不断的滚动替换这两行数据，最终求解出最后一行数据的方式。
关键点：推导计算当前行和下（上）一行的索引。由于数组是滚动的，因此，我们目标行的索引也是随时变化的，以下为求取当前行和上（下）一行的通用公式：

当前行： const curIdx = i % 2
由于我们的滚动数组只有2行，因此，当前索引只要与2求模即可；
上（下）一行：const preIdx = +!curIdx
由于滚动数组只有两行，索引要么是0，要么是1，我们对当前行取反便可得到上（下）一行的索引（注意，在js中，对1取反是false,对0取反是true,因此我们通过一个隐式类型转换将布尔类型转换为数字类型）。

这道题我们要怎么理解呢？我们如果想要爬到第 n 阶楼梯，那么上一步有可能是在 n-1 ,也有可能是在 n-2

​实际使用：后面刷题时会经常用到，详见下文

二、刷题正餐

2.1 LeetCode 120. 三角形最小路径和

2.1.1 解题思路

按照我们之前将的递推套路：
1. 定义递推状态：在这道题中，我们每走一步的路径和主要取决于当前所处的行数i和当前的列数j，因此，我们这道题的递推状态应该是：dp[i, j]
2. 递推公式：确定了递推状态之后，我们就要确定递推公式了。那么，第i行第j列的数据要如何才能推导出来呢？首先，依据题意，我们要求最小路径和，如果我们从最底下往上走，那么我们可以知道，下一行i的数据应该是上一行i+1合法路径的最小值加上当前走到节点的值。
因此，我们得到了如下公式：

// 第i行第j列数据的推导公式
dp[i, j] = min(dp[i+1, j], dp[i+1, j+1]) + val[i,j]

3.分析边界条件：我们需要将我们题目已知的条件初始化到我们的递推数组当中作为边界条件。这道题中，边界条件就是最后一行的数据，我们将最后一行的数据先加入到滚动数组当中，这样之后就可以根据最后一行数据不断的往上推导总路径和，从而找到最小路径。
4. 程序实现：我们直接使用循环加滚动数组技巧实现。

2.1.2 代码演示

function minimumTotal(triangle: number[][]): number {
    const n = triangle.length;
    // 递推公式（状态转义方程）以下为自底向上走的公式
    // dp[i, j] = min(dp[i+1, j], dp[i+1, j+1]) + val[i,j]
    // 由于i只跟i+1有关，因此，我们可以用滚动数组的技巧定义dp数组
    let dp: number[][] = [];
    for(let i=0;i<2;i++){
    dp.push([]);
    }
    // 首先初始化最后一行的数值，由于使用了滚动数组的技巧，因此，我们最后一行的索引应该是(n-1)%2
    for(let i=0;i<n;i++) {
    dp[(n-1)%2][i] = triangle[n-1][i];
    }
    // 然后从倒数第二行开始求值
    for(let i = n-2;i>=0;--i) {
        // 由于使用了滚动数组，因此，当前行的下标为i%2,而下一行的下标则是当前行下标取反
        let idx = i % 2;
        let nextIdx = +!idx;
        // 根据上面的公式计算出每一个位置上的值
        for (let j=0; j <= i; j++) {
            dp[idx][j] = Math.min(dp[nextIdx][j], dp[nextIdx][j + 1]) + triangle[i][j];
        }
    }
    // 最终，三角形顶点的那个值就是我们要求的值
    return dp[0][0];
};

2.2 LeetCode 119. 杨辉三角 II

2.2.1 解题思路

这道题与上一道题类似，依然可以根据上一行推导出下一行的值，因此还是要祭出滚动数组的技巧，递推状态与递推公式的分析也比较类似，大家可以自己尝试推导。
而这一道题的边界条件，其实就是每一行的第一位都应该是1。

2.1.2 代码演示

function getRow(rowIndex: number): number[] {
    const res: number[][] = [];
    // 初始化两行全部初始填充0的滚动数组
    for(let i=0;i<2;i++)res.push(new Array(rowIndex+1).fill(0));
    for(let i=0;i<=rowIndex;i++) {
        // 计算滚动数组当前索引和上一行索引
        let idx = i % 2;
        let preIdx = +!idx;
        res[idx][0] = 1;
        // 计算每一行出第一位外其他位置的值
        for(let j=1;j<=i;j++) {
            res[idx][j] = res[preIdx][j-1] + res[preIdx][j];
        }
    }
    // 滚动数组最后一行
    return res[(rowIndex % 2)]
};

2.3 LeetCode 198. 打家劫舍

2.3.1 解题思路

1. 递推状态分析：
既然要求能够偷到的最多的金额，那么，假设最后一家是n,那么,最大金额与我们是否偷最后一家有直接的关系，我们需要分类讨论：

a. 不偷最后一家：dp[n][0]其中，0代表不偷
b. 偷最后一家：dp[n][1]其中，1代表偷

2. 确定递推公式：
由于递推状态分为两种情况讨论，因此，我们的递推公式，也应该分成两个部分：

a. 不偷最后一家：由于不能连续偷相邻的两家，如果最后一家不偷，那么，我们倒数第二家就可以偷，因此，此时我们的最大收益就取决于偷倒数第二家的金额与不偷倒数第二家金额的最大值。即：dp[n][0] = max(dp[n-1][0], dp[n-1][1])
b. 偷最后一家：由于要偷最后一家，那么就不能偷倒数第二家，因此，这种情况的最大收益是不偷倒数第二家获得的收益加上偷最后一家带来的收益，即dp[n][1] = dp[n-1][0] + nums[n]

3. 确定边界条件：
依据题意，我们如果不偷第一家的时候，因为一家都没偷，此时收益应该为0。如果偷第一家，那么收益就是第一家的钱。至此，我们就确立了最开始的边界条件。
4. 程序实现：
这道题由于当前收益只取决于上一家的收益，因此依然使用滚动数组技巧加循环实现。

2.3.2 代码演示

function rob(nums: number[]): number {
    const n = nums.length;
    // 由于不能连续偷两家，因此，最大收益应该分为两种情况讨论：
    // 1. dp[n][0] = max(dp[n-1][0], dp[n-1][1]) 即：不偷最后一家的最后收益，取决于我偷倒数第二家的收益与不偷倒数第二家的收益的最大值
    // 2. dp[n][1] = dp[n-1][0] + nums[n] 即：如果投了最后一家，那么倒数第二家就不能偷，所以最大收益就等于不偷倒数第二家的收益加上偷最后一家获得的收益
    const dp: number[][] = [];
    for(let i=0;i<2;i++) dp.push([]);
    // 初始化第0家的值
    dp[0][0] = 0;// 不偷第一家时收益为0
    dp[0][1] = nums[0];// 偷第一家时收益为第一家的钱
    for(let i=1;i<n;i++) {
// 使用滚动数组技巧
        let idx = i % 2;
        let preIdx = +!idx;
        dp[idx][0] = Math.max(dp[preIdx][0] , dp[preIdx][1]);
        dp[idx][1] = dp[preIdx][0] + nums[i];
    }
    // 最终收益最大值时不偷最后一家和偷最后一家的最大值
    return Math.max(dp[(n-1) % 2][0], dp[(n-1) % 2][1]);
};

2.4 LeetCode 152. 乘积最大子数组

2.4.1 解题思路

1. 递推状态分析： 我们要求最大子数组的乘积，那么我们可以用 dp[n] 代表最后一位是 n 的最大子数组乘积最大值。
2. 递推公式： 最后一个数是 n 有两种可能性，第一种是让 n-1 的最大乘积再乘上当前n的值，第二种则是 n 不与之前的值相乘，自开一国，因此，我们应该在这两种情况中选一个最大值，所以，递推公式应为：dp[n] = max(dp[n-1] * val[n], val[n])
3. 边界条件：由于数组中可能含有负数，有可能使当前值乘上原先的最大值变成最小值，也可能时当前值乘上原先的最小值变成最大值，因此，我们不仅需要记录当前数字之前的最大值，也要记录最小值，方便处理负数的情况。而初始时，由于我们要求的是乘积关系，那么我们的最大值和最小值都初始化为1即可。
4. 程序实现：由于第 n 项的最大乘积只跟 n-1 有关，我们可以使用变量方式存储关系，不需要额外开辟递推数组空间。

2.4.2 代码演示

function maxProduct(nums: number[]): number {
    // 递推状态：dp[n]代表以n作为结尾的最长连续子数组的乘积
    // 递推公式：dp[n] = max(dp[n-1] * val[n], val[n]),即这个有两种可能，一种是以n作为结尾，然后乘上之前的最大值，另一种是不乘之前的值，自己独立成为一个结果
    // 我们应该从这两种方案中选择一个较大的值作为结果
    // 由于当前值只跟上一个值有关，我们可以使用变量方式来替代递推数组，又因为数组中可能存在负数，有可能导致当前值乘上之前的最大值变成了最小值，因此，我们
    // 还需要额外记录一下数组中的最小值
    let res = Number.MIN_SAFE_INTEGER;
    // 由于是乘积关系，因此，最小值和最大值初始化为1
    let min = 1;
    let max = 1;
    for(let num of nums) {
        // 由于num是小于0的，因此，如果我们依然乘以原先的最大值，那就可能反而变成最小值，因此当num小于0时，我们交换最大值和最小值，这样，num乘以原先的最小值，就可以得到较大值了
        if(num < 0) [min, max] = [max, min];
        // 计算最大值和最小值
        min = Math.min(min * num, num);
        max = Math.max(max * num, num);
        // 最终结果在上一个结果和max间取最大值
        res = Math.max(res, max);
    }
    return res;
};

2.5 LeetCode 322. 零钱兑换

2.5.1 解题思路

1. 递推状态：我们使用多少个硬币，取决于要凑的金额的面额有多大，因此，我们的递推状态为：dp[n]
2. 递推公式：假如我们要凑的面额是n，那么我们能凑够的最小的硬币数量应该是n-coin面额硬币数量再加上当前这枚硬币coin的数量1，并且每次都取最少的数量即可。因此，我们最终的递推公式应该是：dp[n] = min(dp[i-coin] + 1)，即面额为n的钱需要我们在所有的拼凑方案中，取一个最小值，而每一个拼凑方案应该是当前面额i减去当前使用的硬币面额coin再加上当前硬币的数量1。
3. 边界条件：当面额为0时，我们需要0枚硬币。
4. 程序实现：我们再拼凑面额的时候，有一些特殊情况需要考虑，如：如果当前要拼凑的面额比硬币的面额要小，那么我们无法使用当前硬币拼凑成目标面额如果i-coin面额都无法拼凑成功的话，那么我们肯定也无法使用coin面额的硬币拼凑出目标面额，因为i-coin是前置条件。

2.5.2 代码演示

function coinChange(coins: number[], amount: number): number {
    // 我们需要计算出每一个面额所需要的硬币数量
    let dp: number[] = new Array(amount+1);
    // 初始时全部填充为-1代表不可达
    dp.fill(-1);
    // 拼凑0元需要0枚硬币
    dp[0] = 0;
    // 循环每一个面额
    for(let i=1;i<=amount;i++) {
        for(let coin of coins) {
            // 如果当前要拼凑的面额比当前硬币还小，那就不能使用当前硬币
            if(i < coin) continue;
            // 如果没办法拼凑到dp[i-coin]的硬币，那么自然也不可能使用coin面额的硬币拼凑到dp[i]
            if(dp[i - coin] === -1) continue;
            // 如果当前的匹配方案没有使用过，或者使用当前匹配方案的结果比上一个匹配方案的结果大，说明我们找到了更小的拼凑方案，那么我们就把当前拼凑方案替换之前的拼凑方案
            if(dp[i] === -1 || dp[i] > dp[i - coin] + 1) dp[i] = dp[i - coin]+1;
        }
    }
    return dp[amount];
};
 

2.6 LeetCode 300. 最长递增子序列

2.6.1 解题思路

概念扫盲：
a. 递增子序列：
你可以在一个完整的序列中，“跳着”选择元素，并且下一个元素必须不能小于上一个元素。所谓“跳着”，就是指元素索引不需要连续，如下面示例：

`# 原始序列
1, 4, 2, 2, 3, 5, 0, 6
# 递增子序列
1, 2, 2, 3, 5, 6`

b. 严格最长递增子序列：
严格递增子序列是在递增子序列的基础上多了一个限定条件，就是下一个元素不能等于上一个元素，只能大于，如下示例：

# 原始序列
1, 4, 2, 2, 3, 5, 0, 6

# 严格递增子序列
1, 2, 3, 5, 6

1. 递推状态：由于我们最长递增子序列的长度与我当前以哪个元素作为最后一个元素有关，因此，我们的递推状态为：dp[n]，代表以n位置作为结尾的最长递增子序列的长度
2. 递推公式：我们要算出以第n个元素作为结尾的最长递增子序列的长度，就要找出他上一个合法的最长递增子序列的最后一个元素j,而我们第n个元素作为结尾的最长递增子序列长度就是上一个最长递增子序列长度加一,我们只需要将所有满足这个条件的最长递增子序列长度的最大值求出来就是最终的结果，即：dp[n] = max(dp[j] + 1) | j<n & val(j) < val(n)
3. 边界条件：n为1时，最长递增子序列长度为1
4. 程序实现：由于我们的递归状态定义的是以n作为结尾的最长递增子序列的长度，因此，我们每一项的初始值默认都是1，至少要选择当前的数。

2.6.2 代码演示

function lengthOfLIS(nums: number[]): number {
    const dp: number[] = [];
    let res: number = Number.MIN_SAFE_INTEGER;
    for(let i=0;i<nums.length;i++) {
 // 每一项都初始化为1，因为dp[i]代表以i位置作为结尾的最长递增子序列的长度，那我们最少都应该选择i这个数，长度就是1
        dp[i] = 1;
        // 在i位置之前找到满足nums[j] < num[i]的值
        for(let j = 0; j < i;j++) {
            if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        // 到此，我们已经找到了一组最长递增子序列了，更新一下res
        res = Math.max(res, dp[i]);
    }
    return res;

今天的刷题到此暂告一段落。
从上面刷的几道题其实我们不难发现，无论是递推算法还是动态规划，都有一定的套路可循，虽然这个套路学起来也并不简单，但是至少有了明确的学习方向，我们可以通过：递推状态定义、递推公式（状态转移方程）推导、边界条件确立、程序实现这四个通用套路将一个看似复杂的递推或动规程序逐一分析解决。
当然，上面的程序实现，为了更容易理解，没有使用太多的技巧进行优化，并不一定是最优的，未来如果有机会，将和大家分享动态规划的优化技巧。也欢迎大家与我们多多交流~

-END-