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

youdao

ydtech

youdao

ydtech

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

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];
};

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)]
};

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]);
};

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;
};

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];
};

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;
};