动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动规是由前一个状态推导出来的，而贪心是局部直接选最优的，

状态转移方程

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

509. 斐波那契数

dp[i]:第i个斐波那契数

  1. var fib = function(n) {
  2.     let dp= [0,1];
  3.     for(let i = 2; i <= n; i++) {
  4.         dp[i] = dp[i - 1] + dp[i - 2]
  5.     }
  6.     return dp[n]
  7. };

70. 爬楼梯

image.png

  3. dp[i]:第i阶的走法
  4. dp[i] = dp[i-1] + dp[i-2]
  6. 从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
  7. dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
  8. dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
  12. dp[3] = 3;
  13. dp[4] = 5;// 1,1,1,1  1,2,1   2,2   1,1,2  2,1,1
  1. var climbStairs = function (n) {
  4.   let dp = [];
  5.   dp[1] = 1;
  6.   dp[2] = 2;
  10.   for (let i = 3; i <= n; i++) {
  11.     dp[i] = dp[i - 1] + dp[i - 2];
  12.   }
  13.   return dp[n]
  14. };

746. 使用最小花费爬楼梯

image.png

  1. dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]。
  2. dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

image.png

  1. var minCostClimbingStairs = function(cost) {
  2.     const dp = [ cost[0], cost[1] ]
  4.     for (let i = 2; i < cost.length; ++i) {
  5.         dp[i] = Math.min(dp[i -1] + cost[i], dp[i - 2] + cost[i])
  6.     }
  8.     return Math.min(dp[cost.length - 1], dp[cost.length - 2])
  9. };

62. 不同路径

image.png

  1. var uniquePaths = function(m, n) {
  2.     let dp = new Array(m).fill(1).map(() => new Array(n).fill(1));
  3.     // dp[i][j] 表示到达（i，j） 点的路径数
  4.     for (let i=1; i<m; i++) {
  5.         for (let j=1; j< n;j++) {
  6.             dp[i][j]=dp[i-1][j]+dp[i][j-1];
  7.         }
  8.     }
  9.     return dp[m-1][n-1];
  10. };

63. 不同路径 II

image.png
障碍处理：
将二维数组初始化填充0，遇到障碍1忽略

  1. var uniquePathsWithObstacles = function(obstacleGrid) {
  2.     const m = obstacleGrid.length
  3.     const n = obstacleGrid[0].length
  4.     const dp = Array(m).fill().map(item => Array(n).fill(0))
  6.     for (let i = 0; i < m && obstacleGrid[i][0] === 0; ++i) {
  7.         dp[i][0] = 1
  8.     }
  10.     for (let i = 0; i < n && obstacleGrid[0][i] === 0; ++i) {
  11.         dp[0][i] = 1
  12.     }
  14.     for (let i = 1; i < m; ++i) {
  15.         for (let j = 1; j < n; ++j) {
  16.             dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]
  17.         }
  18.     }
  20.     return dp[m - 1][n - 1]
  21. };

198. 打家劫舍

image.png
image.png

  1. dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
  3. 如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
  5. 如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）
  7. 然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
  1. var rob = function(nums) {
  2.     let dp = [];
  3.     dp[0] = nums[0];
  4.     dp[1] = Math.max(dp[0],nums[1]);
  5.     for(let i=2;i<nums.length;i++){
  6.         dp[i] = Math.max((dp[i-2]+nums[i]),dp[i-1])
  7.     }
  8.     return dp[nums.length-1]
  9. };

213. 打家劫舍 II

环形

  1. //此题为一个环，所以两端不可并行探索，所以分为两种情况，
  2. //第一种 探索 0 - （length - 2）
  3. //第二种 探索 1 - （length - 1）
  4. var rob = function(nums) {
  5.     //特殊情况
  6.     const len = nums.length
  7.     if (len === 0) return 0
  8.     if (len === 1) return nums[0]
  9.     if (len === 2) return Math.max(nums[0], nums[1])
  11.     const rob = function(nums, start, end) {
  12.         let dp=[];
  13.         dp[start] = nums[start];
  14.         dp[start+1] = Math.max(dp[start],nums[start+1])
  17.         for (let i = start + 2; i <= end; i++) {
  18.             dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])
  20.         }
  22.         return dp[end]
  23.     }
  25.     return Math.max(rob(nums, 0, len-2), rob(nums, 1, len-1))    
  26. };

121. 买卖股票的最佳时机

贪心

  1. var maxProfit = function(prices) {
  2.     let lowPrice = prices[0];
  3.     let profit = 0;
  5.     for(let i = 0;i<prices.length;i++){
  6.         lowPrice = prices[i]<lowPrice?prices[i]:lowPrice;
  7.         profit = Math.max(profit, prices[i] - lowPrice);// 遍历一趟就可以获得最大利润
  8.     }
  9.     return profit
  10. };

DP

0-1背包 ???

image.png
image.png
输入 value = [15,20,30], weight = [1,3,4], size = 4；

  1. 示例：
  3. 输入：W = 5, N = 3
  4.      w = [3, 2, 1], v = [5, 2, 3]
  5. 输出：8
  6. 解释：选择 i=0 和 i=2 这两件物品装进背包。它们的总重量 4 小于 W，同时可以获得最大价值 8。

image.png

  • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
  • 放物品i：装第 i 个物品，就要寻求剩余重量 [j - weight[i]] 限制下的最大价值，加上第i个物品的价值value[i], 由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值 ```javascript dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少 如果 dp[3][5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  1. 如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0<br />dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值
  3. 那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。<br />当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/248010/1635421043147-6ede11ae-9ce1-4725-af82-b79493c22185.png#clientId=u8f4c4044-df22-4&from=paste&height=343&id=u40ea9b75&margin=%5Bobject%20Object%5D&name=image.png&originHeight=686&originWidth=1240&originalType=binary&ratio=1&size=168225&status=done&style=none&taskId=u3a1f0843-947f-4968-a3f9-e1a9c9ff4cd&width=620)
  4. ```javascript
  5. function testWeightBagProblem (wight, value, size) {
  6.   const len = wight.length, 
  7.     dp = Array.from({length: len + 1}).map(
  8.       () => Array(size + 1).fill(0)
  9.     );
  11.   for(let i = 1; i <= len; i++) { //遍历物品 注意:索引从1开始
  12.     for(let j = 0; j <= size; j++) { //遍历背包容量
  13.       //没有超出背包容量     由于 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]，这一点不要搞混。
  14.       if(wight[i - 1] <= j) {
  15.         dp[i][j] = Math.max(
  16.           dp[i - 1][j], 
  17.           value[i - 1] + dp[i - 1][j - wight[i - 1]]
  18.         )
  19.       } else {
  20.         //超出背包容量
  21.         dp[i][j] = dp[i - 1][j];
  22.       }
  23.     }
  24.   }
  26. //   console.table(dp);
  28.   return dp[len][size];
  29. }
  31. function testWeightBagProblem2 (wight, value, size) {
  32.   const len = wight.length, 
  33.     dp = Array(size + 1).fill(0);
  34.   for(let i = 1; i <= len; i++) {
  35.     for(let j = size; j >= wight[i - 1]; j--) {
  36.       dp[j] = Math.max(dp[j], value[i - 1] + dp[j - wight[i - 1]]);
  37.     }
  38.   }
  39.   return dp[size];
  40. }
  43. function test () {
  44.   console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
  45. }
  47. test();

416. 分割等和子集 ??

image.png

  1. //思路: 0-1背包
  2. // 1. 背包容量 sum/2
  3. // 2. 每一个物品只能装一次,如果出现背包中重量等于sum/2则为true else false
  4. // 3. dp[i][j]=x  是否存在：nums区间[0, i] 中取一些元素，使其和为j
  5. // 4. dp[i][j] =  dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]; 选择第i个元素|不选择第i个元素 元素索引从1开始，第i个元素的重量是对应的i-1
  6. // 5. 初始化 dp[0][j]代表不选物品能否将背包装满 显然为false dp[i][0]代表背包容量为0 显然true
  8. var canPartition = function (nums) {
  9.   let sum = nums.reduce((acc, num) => acc + num, 0);
  10.   //奇数不能够平分两个数组
  11.   if (sum % 2) {
  12.     return false;
  13.   } else {
  14.     sum = sum / 2;
  15.   }
  17.   const dp = Array.from(nums).map(() =>
  18.     Array.from({ length: sum + 1 }).fill(false)
  19.   );
  21.   for (let i = 0; i < nums.length; i++) {
  22.     dp[i][0] = true;
  23.   }
  25.   for (let i = 0; i < dp.length - 1; i++) {
  26.     for (let j = 0; j < dp[0].length; j++) {
  27.       dp[i + 1][j] =
  28.         j - nums[i] >= 0 ? dp[i][j] || dp[i][j - nums[i]] : dp[i][j];
  29.     }
  30.   }
  31.   return dp[nums.length - 1][sum];
  32. };
  1. /**
  2.  * @param {number[]} nums
  3.  * @return {boolean}
  4.  * 背包问题：看数组中是否存在加起来为sum/2的数.
  5.  * 背包容量（V） = sum/2
  6.  * 每一个物品只能装一次,如果出现背包中重量等于sum/2则为true else false
  7.  * dp[i]表示能否填满容量为i的背包
  8.  * 状态转移方程为 dp[j] = dp[j] || dp[j-nums[i]]
  9.  * 举例:v = sum/2 = 11   nums = [1,5,11,5]  1是true 0 是false
  10.  *          0  1  2  3  4  5  6  7  8  9  10  11
  11.  *  nums[0] 0  1  0  0  0  0  0  0  0  0   0   0
  12.  *  nums[1] 0  1  0  0  0  1  1  0  0  0   0   0
  13.  *  nums[2] 0  1  0  0  0  1  1  0  0  0   0   1
  14.  *  nums[3] 0  1  0  0  0  1  1  0  0  0   0   1
  15.  * 
  16.  * 所以返回true，因为背包中nums[i]的状态都是由上一行决定的因此可以将二维转化为1维数组从尾部开始
  17.  */
  18. var canPartition = function (nums) {
  19.   let sum = nums.reduce((acc, num) => acc + num, 0);
  20.   if (sum % 2) {
  21.     return false;
  22.   }
  23.   sum = sum / 2;
  24.   const dp = Array.from({ length: sum + 1 }).fill(false);
  25.   dp[0] = true;
  27.   for (let i = 0; i < nums.length; i++) {
  28.     for (let j = sum; j > 0; j--) {
  29.       dp[j] = dp[j] || (j - nums[i] >= 0 && dp[j - nums[i]]);
  30.     }
  31.   }
  32.   return dp[sum];
  33. };

1049. 最后一块石头的重量 II ???

image.png

  1. var lastStoneWeightII = function (stones) {
  2.     let sum = stones.reduce((s, n) => s + n);
  4.     let dpLen = Math.floor(sum / 2);
  5.     let dp = new Array(dpLen + 1).fill(0);
  7.     for (let i = 0; i < stones.length; ++i) {
  8.         for (let j = dpLen; j >= stones[i]; --j) {
  9.             dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
  10.         }
  11.     }
  13.     return sum - dp[dpLen] - dp[dpLen];
  14. };

300. 最长递增子序列

image.png

  1. dp[i]表示i之前包括i的最长上升子序列的长度
  2. dp[i] = max(dp[i], dp[j] + 1);
  3. if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
  1. var lengthOfLIS = function(nums) {
  2.     let dp = Array(nums.length).fill(1);
  3.     let result = 1;
  5.     for(let i = 1; i < nums.length; i++) {
  6.         for(let j = 0; j < i; j++) {
  7.             if(nums[i] > nums[j]) {
  8.                 dp[i] = Math.max(dp[i], dp[j]+1);
  9.             }
  10.         }
  11.         result = Math.max(result, dp[i]);
  12.     }
  13.     return result;
  15. };

674. 最长连续递增序列

image.png

  1. var findLengthOfLCIS = function(nums) {
  2.     let dp = new Array(nums.length).fill(1);
  4.     for(let i=1; i<nums.length;i++){
  5.         if(nums[i]>nums[i-1]){
  6.             dp[i] = dp[i-1]+1
  7.         } 
  8.     }
  9.     return Math.max(...dp);
  10. };

718. 最长重复子数组

image.png

//dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
const findLength = (A, B) => {
    // A、B数组的长度
    const [m, n] = [A.length, B.length];
    // dp数组初始化，都初始化为0
    const dp = new Array(m + 1).fill(0).map(x => new Array(n + 1).fill(0));
    // 初始化最大长度为0
    let res = 0;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 遇到A[i - 1] === B[j - 1]，则更新dp数组
            if (A[i - 1] === B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            // 更新res
            res = dp[i][j] > res ? dp[i][j] : res;
        }
    }
    // 遍历完成，返回res
    return res;
};

1143. 最长公共子序列

image.png

const longestCommonSubsequence = (text1, text2) => {
    let dp = Array.from(Array(text1.length+1), () => Array(text2.length+1).fill(0));

    for(let i = 1; i <= text1.length; i++) {
        for(let j = 1; j <= text2.length; j++) {
            if(text1[i-1] === text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] +1;;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    return dp[text1.length][text2.length];
};

1035. 不相交的线

image.png

直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。

其实也就是说A和B的最长公共子序列是[1,4]，长度为2。 这个公共子序列指的是相对顺序不变（即数字4在字符串A中数字1的后面，那么数字4也应该在字符串B数字1的后面）
这么分析完之后，大家可以发现：本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！1143

const maxUncrossedLines = (nums1, nums2) => {
    // 两个数组长度
    const [m, n] = [nums1.length, nums2.length];
    // 创建dp数组并都初始化为0
    const dp = new Array(m + 1).fill(0).map(x => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 根据两种情况更新dp[i][j]
            if (nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // 返回dp数组中右下角的元素
    return dp[m][n];
};

53. 最大子序和

image.png

dp[i]：包括下标i之前的最大连续子序列和为dp[i]。

dp[i]只有两个方向可以推出来：

dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和

nums[i]，即：从头开始计算当前连续子序列和

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

image.png

var maxSubArray = function(nums) {
    if(nums.length == 0) return 0;
    var dp=[];
    dp[0]=nums[0];
    var max = dp[0];
    for(var i=1;i<nums.length;i++){
        dp[i] = Math.max(nums[i],dp[i-1]+nums[i] );
        max = Math.max(dp[i],max)

    }
    return max;  
};

392. 判断子序列

image.png

参见分析

const isSubsequence = (s, t) => {
    // s、t的长度
    const [m, n] = [s.length, t.length];
    // dp全初始化为0
    const dp = new Array(m + 1).fill(0).map(x => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 更新dp[i][j]，两种情况
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }
    // 遍历结束，判断dp右下角的数是否等于s的长度
    return dp[m][n] === m ? true : false;
};

115. 不同的子序列

image.png
参见

583. 两个字符串的删除操作

image.png

const minDistance = (word1, word2) => {
    let dp = Array.from(Array(word1.length + 1), () => Array(word2.length+1).fill(0));

    for(let i = 1; i <= word1.length; i++) {
        dp[i][0] = i; 
    }

    for(let j = 1; j <= word2.length; j++) {
        dp[0][j] = j;
    }

    for(let i = 1; i <= word1.length; i++) {
        for(let j = 1; j <= word2.length; j++) {
            if(word1[i-1] === word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 2);
            }
        }
    }

    return dp[word1.length][word2.length];
};

72. 编辑距离
image.png

参考链接

const minDistance = (word1, word2) => {
    let dp = Array.from(Array(word1.length + 1), () => Array(word2.length+1).fill(0));

    for(let i = 1; i <= word1.length; i++) {
        dp[i][0] = i; 
    }

    for(let j = 1; j <= word2.length; j++) {
        dp[0][j] = j;
    }

    for(let i = 1; i <= word1.length; i++) {
        for(let j = 1; j <= word2.length; j++) {
            if(word1[i-1] === word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1);
            }
        }
    }

    return dp[word1.length][word2.length];
};

647. 回文子串

image.png
参考链接

const countSubstrings = (s) => {
    const strLen = s.length;
    let numOfPalindromicStr = 0;
    let dp = Array.from(Array(strLen), () => Array(strLen).fill(false));

    for(let j = 0; j < strLen; j++) {
        for(let i = 0; i <= j; i++) {
            if(s[i] === s[j]) {
                if((j - i) < 2) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i+1][j-1];
                }
                numOfPalindromicStr += dp[i][j] ? 1 : 0;
            }
        }
    }

    return numOfPalindromicStr;
}



双指针法：

const countSubstrings = (s) => {
    const strLen = s.length;
    let numOfPalindromicStr = 0;

    for(let i = 0; i < 2 * strLen - 1; i++) {
        let left = Math.floor(i/2);
        let right = left + i % 2;

        while(left >= 0 && right < strLen && s[left] === s[right]){
            numOfPalindromicStr++;
            left--;
            right++;
        }
    }

    return numOfPalindromicStr;
}

516. 最长回文子序列

image.png
参考链接

const longestPalindromeSubseq = (s) => {
    const strLen = s.length;
    let dp = Array.from(Array(strLen), () => Array(strLen).fill(0));

    for(let i = 0; i < strLen; i++) {
        dp[i][i] = 1;
    }

    for(let i = strLen - 1; i >= 0; i--) {
        for(let j = i + 1; j < strLen; j++) {
            if(s[i] === s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }

    return dp[0][strLen - 1];
};