适用场景： 最优子结构、无后效性和重复子问题

:::warning

经典问题：

步骤：

  1. 根据状态， 确定状态转移方程
  2. （根据状态方程）， 确定初识值、边界。。。

练习1: 经典

70. 爬楼梯

dp[i] = dp[i-1] + dp[i -2]
更优解

  1. [a, b] = [b, a + b];

爬楼梯： 面试题 08.01. 三步问题

更优解

  1. [a, b, c] = [b, c, (a + b + c) % 1000000007];

剑指 Offer 46. 把数字翻译成字符串

0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
计算一个数字有多少种不同的翻译方法？

  1. 从前高位到低位依次获取数字
  2. 动态规划, 限制prev != 0 && prev * 10 + cur <= 25
      1. 合法 dp[n] = dp[n-1] + dp[n-2]
      1. 不合法 dp[n] = dp[n-1]

case 1: 12258 => 5
prev, cur, prev * 10 + cur
0 1 1
1 2 12
2 2 22
2 5 25
5 8 58
[ 0, 1, 1, 2, 3, 5, 5]
📢 case : 506 => 1 ，额外判断不合法限制

  1. var translateNum = function(num) {
  2.     let len = String(num).length;
  3.     let base = 10 ** (len-1);
  4.     let dp = [0, 1];
  5.     let prev = 0, cur = 0;
  6.     for (let i=2; i < len+2; i++) {
  7.         prev = cur;
  8.         cur = Math.floor(num / base);
  9.         num = num % base;
  10.         base /= 10;
  11.         dp[i] = dp[i-1];
  12.         if (i > 2 && prev != 0 && (prev * 10 + cur) <= 25) {
  13.             dp[i] += dp[i-2];
  14.         }
  15.     }
  16.     return dp.pop();
  17. };

剑指 Offer 42. 连续子数组的最大和（53. 最大子序和）

状态方程： dp[i] = Math.max(dp[i-1]+nums[i], nums[i])

  1. var maxSubArray = function(nums) {
  2.     let dp = new Array(nums.length).fill(null);
  3.     dp[0] = nums[0];
  4.     for (let i = 1; i <nums.length; i++) {
  5.         dp[i] = Math.max(dp[i-1]+nums[i], nums[i])
  6.     }
  7.     // console.log(dp)
  8.     return Math.max(...dp);
  9. };

剑指 Offer 63. 股票的最大利润（121. 买卖股票的最佳时机）

状态方程： dp[i] = Math.max(dp[i-1], prices[i] - minPrice)

  1. var maxProfit = function(prices) {
  2.     let dp = new Array(prices.length).fill(null)
  3.     dp[0] = 0;
  4.     for (let i = 1; i < prices.length; i++) {
  5.         let minPrice = Math.min(...prices.slice(0, i));
  6.         dp[i] = Math.max(dp[i-1], prices[i] - minPrice);
  7.     }
  8.     // console.log(dp)
  9.     return Math.max(...dp)
  10. };

常规做法：

  1. var maxProfit = function(prices) {
  2.    // 最多只允许完成一笔交易
  3.    let res = 0;
  4.    let min = prices[0];
  5.    for (let i = 1; i< prices.length; i++) {
  6.        let cur = prices[i];
  7.        if (cur > min && cur - min > res) {
  8.            res = cur - min;
  9.        }
  10.        if (cur < min) {
  11.            min = cur
  12.        }
  13.    }
  14.    return res;
  15. };

198. 打家劫舍

状态方程： dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i])

  1. var rob = function(nums) {
  2.     if (nums.length == 0) return 0;
  3.     if (nums.length < 3) return Math.max(...nums);
  4.     let dp = new Array(nums.length).fill(0);
  5.     dp[0] = nums[0];
  6.     dp[1] = Math.max(nums[0], nums[1]); // 易错点
  7.     for (let i=2; i<nums.length; i++) {
  8.         dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i])
  9.     }
  10.     return dp.pop();
  11. };

322. 零钱兑换

状态方程：dp[i] = Math.min(dp[i], dp[i-coin] + 1);
⚠️ 嵌套循环

  1. var coinChange = function(coins, amount) {
  2.     var dp = new Array(amount+1).fill(amount+1);
  3.     dp[0] = 0;
  4.     for (var i = 1; i < amount+1; i++) {
  5.         for (var coin of coins) {
  6.             if (i >= coin ) {
  7.                 dp[i] = Math.min(dp[i], dp[i-coin] + 1);
  8.             }
  9.         }
  10.     }
  11.     var res = dp.pop();
  12.     return res > amount ? -1 :  res;
  13. };

练习2: 数列

509. 斐波那契数

状态方程： dp[i] = i < 2 ? i : dp[i - 1] + dp[i - 2]
⚠️ 开始的两位数[0, 1]

  1. var fib = function(N) {
  2.     var dp = [];
  3.     for (var i = 0; i <= N; i++) {
  4.         dp[i] = i < 2 ? i : dp[i - 1] + dp[i - 2]
  5.     }
  6.     // console.log(dp)
  7.     return dp.pop()
  8. };

1137. 第 N 个泰波那契数

状态方程： dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
⚠️ 开始的三位数 [0, 1, 1]

  1. var tribonacci = function(n) {
  2.     let len = Math.max(2, n+1);
  3.     let dp = new Array(len).fill(null);
  4.     dp[0] = 0;
  5.     dp[1] = 1;
  6.     dp[2] = 1;
  7.     if (n<3) return dp[n];
  8.     for (let i=3; i<=n; i++) {
  9.         dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
  10.     }
  11.     return dp.pop()
  12. };

练习3:

剑指 Offer 14- I. 剪绳子(343. 整数拆分)

  • 2 <= n <= 58

状态方程： dp[i] = Math.max(dp[i], j dp[i-j], j (i - j))
⚠️ 内部嵌套的边界

  1. var cuttingRope = function(n) {
  2.     let dp = new Array(n+1).fill(0)
  3.     dp[0] = 0;
  4.     dp[1] = 1;
  5.     for (let i = 2; i <= n; i++) {
  6.         for (let j = 1; j < i; j++) {
  7.             dp[i] = Math.max(dp[i], j * dp[i-j], j * (i - j))
  8.         }
  9.     }
  10.     // console.log(dp);
  11.     return dp[n]
  12. };

剑指 Offer 14- II. 剪绳子 II

剑指 Offer 49. 丑数(264. 丑数 II)

优化： 三指针+动态规划
分析： 由2， 3，5组合乘积， 第n个数由第x个数*（2｜3｜5）组成。第x数，可能有三种， 故是3个指针。

  1. var nthUglyNumber = function(n) {
  2.     // 三指针+动态规划
  3.     let dp = new Array(n).fill(1);
  4.     let a = 0, b = 0, c = 0;
  5.     for (let i = 1; i < n; i ++) {
  6.         dp[i] = Math.min(dp[a] * 2, dp[b] * 3, dp[c] * 5);
  7.         // 注意， 出现重复乘积，可能多个指针同时移动
  8.         if (dp[i] == dp[a] * 2) {
  9.             a++;
  10.         }
  11.         if (dp[i] == dp[b] * 3) {
  12.             b++;
  13.         }
  14.         if (dp[i] == dp[c] * 5) {
  15.             c++;
  16.         }
  17.     }
  18.     // console.log(dp)
  19.     return dp.pop();
  20. };

练习4:

面试题 16.17. 连续数列

动态规划， dp保存当前位置结束的连续子序列和的最大值
dp[i+1] = Math.max(dp[i] + cur, cur);

  1.  var maxSubArray = function(nums) {
  2.     let dp = [-Infinity];
  3.     for (let i = 0; i < nums.length; i++) {
  4.         let cur = nums[i];
  5.         dp[i+1] = Math.max(dp[i] + cur, cur);
  6.     }
  7.     return Math.max(...dp);
  8. };

279. 完全平方数

  1. function numSquares(n: number): number {
  2.     let dp = new Array(n + 1).fill(0);
  3.     for (let i = 1; i <= n; ++i) {
  4.         let min = Infinity;
  5.         for (let j = 1; j * j <= i; ++j) {
  6.             min = Math.min(min, dp[i - j * j]);
  7.         }
  8.         dp[i] = min + 1;
  9.     }
  10.     return dp.pop();
  11. };

完成记录

983. 最低票价

837. 新 21 点