这个系列感觉有点大了，而且也特别有套路的感觉
image.png

322. 零钱兑换

image.png

  1. var coinChange = function(coins, amount) {
  2.     const dp = new Array(amount + 1).fill(Infinity); // 多一项
  3.     dp[0] = 0; // 凑出0元，不需要硬币
  5.     for (let i = 1; i <= amount; i++) { // 从 1 元开始凑
  6.         for (let coin of coins) {
  7.             if (i - coin < 0) { // 不能选这个硬币
  8.                 continue; 
  9.             }
  10.             dp[i] = Math.min(dp[i], dp[i - coin] + 1); // 这样算最小的技巧
  11.         }
  12.     }
  14.     return dp[amount] !== Infinity ? dp[amount] : -1;
  15. };


300. 最长递增子序列

image.png
缩小问题范围。

  1. var lengthOfLIS = function(nums) {
  2.     let n = nums.length;
  3.     if (n <= 1) {
  4.         return n;
  5.     }
  7.     let dp = new Array(n).fill(1);
  9.     for (let i = 1; i < n; i++) {
  10.         // 前 i - 1 个数里，比 nums[i] 小的数对应的 dp 最大的数
  11.         for (let j = 0; j <= i - 1; j++) {
  12.             if (nums[j] < nums[i]) {
  13.                 dp[i] = Math.max(dp[i], dp[j]) + 1;
  14.             }
  15.         }
  16.     }
  18.     return Math.max(...dp);
  19. };

279. 完全平方数

image.png
状态转移方程的寻找，之前局限于 i 到 i - 1，通过这道题我们知道还可以跳跃： i 到 j ( 1 <= j <= i * i)

  1. var numSquares = function(n) {
  2.     const dp = (new Array(n + 1)).fill(0); // 初始值边界应该多少？自己应该去举例
  4.     for (let i = 1; i <= n; i++) { // 下标的取法，也要去试验
  5.         let min = Infinity;
  6.         for (let j = 1; j * j <= i; j++) { // dp 的上一步需要取最小才行
  7.             if (min > dp[i - j * j]) {
  8.                 min = dp[i - j * j];
  9.             }
  10.         }
  12.         dp[i] = min + 1;
  13.     }
  15.     return dp[n];
  16. };

96. 不同的二叉搜索树

  1. var numTrees = function(n) {
  2.     let dp = new Array(n + 1).fill(0);
  3.     dp[0] = 1;
  4.     dp[1] = 1;
  6.     for (let i = 2; i <= n; i++) {
  7.         for (let j = 0; j < i; j++) { 
  8.             dp[i] += dp[j] * dp[i - 1 - j]; // 就是硬找规律
  9.         }
  10.     }
  12.     return dp[n];
  13. };

矩阵 和 路径

64. 最小路径和

以相邻的块 决定 下一个 dp 的值

  1. var minPathSum = function(grid) {
  2.     let rows = grid.length;
  3.     let cols = grid[0].length;
  5.     let dp = new Array(rows).fill(-1).map(() => new Array(rows).fill(-1)); // 题目要求 非负
  7.     for (let row = rows - 1; row >= 0; row--) {
  8.         for (let col = cols - 1; col >= 0; col--) {
  9.             let bottom = (row + 1 < rows) ? dp[row + 1][col] : Infinity;
  10.             let right = (col + 1 < cols)  ? dp[row][col + 1] : Infinity;
  11.             let min = Math.min(bottom, right);
  12.             dp[row][col] = (min === Infinity ? 0 : min) + grid[row][col];
  13.         }
  14.     }
  16.     return dp[0][0];
  17. };

但是，也有 dfs 思路：
岛屿问题中经常使用的思路。

  1. var minPathSum = function(grid) {
  2.     let rows = grid.length;
  3.     let cols = grid[0].length;
  5.     let ans = [];
  6.     function dfs(path, row, col) {
  7.         if (row === rows - 1 && col === cols - 1) {
  8.             let sum = path.reduce((pre, cur) => pre + cur, 0) + grid[row][col];
  9.             ans.push(sum);
  10.             return;
  11.         }
  12.         if (!(0 <= row && row < rows && 0 <= col && col < cols)) {
  13.             return;
  14.         }
  16.         // 回溯的那感觉啊
  17.         dfs([...path, grid[row][col]], row, col + 1);
  18.         dfs([...path, grid[row][col]], row + 1, col);
  19.     }
  21.     dfs([], 0, 0);
  23.     return Math.min(...ans);
  24. };

62. 不同路径

  1. var uniquePaths = function(m, n) {
  2.     if (m === 1 || n === 1) {
  3.         return 1;
  4.     }
  6.     let dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
  8.     for (let row = m - 1; row >= 0; row--) {
  9.         for (let col = n - 1; col >= 0; col--) {
  10.             if (row === (m - 1) || col === (n - 1)) {
  11.                 dp[row][col] = 1;
  12.                 continue;
  13.             }
  15.             dp[row][col] = dp[row + 1][col] + dp[row][col + 1];
  16.         }
  17.     }
  19.     return dp[0][0];
  20. };

63. 不同路径 II

和 62 差不多的解法。

  1. var uniquePathsWithObstacles = function(obstacleGrid) {
  2.     let m = obstacleGrid.length;
  3.     let n = obstacleGrid[0].length;
  5.     if (m === 1 || n === 1) {
  6.         let tmp = obstacleGrid.flat();
  7.         if (tmp.includes(1)) {
  8.             return 0;
  9.         }
  10.         return 1;
  11.     }
  13.     let dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
  15.     for (let row = m - 1; row >= 0; row--) {
  16.         for (let col = n - 1; col >= 0; col--) {
  17.             if (obstacleGrid[row][col] === 1) {
  18.                 dp[row][col] = 0
  19.                 continue;
  20.             }
  22.             if ((row === m - 1) && (col === n - 1)) {
  23.                 dp[row][col] = 1;
  24.                 continue;
  25.             }
  27.             if (row + 1 >= m) {
  28.                 dp[row][col] = dp[row][col + 1];
  29.             } else if (col + 1 >= n) {
  30.                 dp[row][col] = dp[row + 1][col];
  31.             } else {
  32.                 dp[row][col] = dp[row + 1][col] + dp[row][col + 1];
  33.             }
  34.         }
  35.     }
  37.     return dp[0][0];
  39. };

45. 跳跃游戏 II

  1. var jump = function(nums) {
  2.     let n = nums.length;
  4.     let dp = new Array(n).fill(Infinity);
  5.     dp[n - 1] = 0; // 边界条件写明白
  7.     for (let i = n - 2; i >= 0; i--) {
  8.         let cur = nums[i];
  9.         if (cur === 0) {
  10.             dp[i] = Infinity;
  11.         } else {
  12.             let min = Infinity;
  13.             for (let j = 1; (j <= cur && j < n); j++) { // 递归算步伐
  14.                 if (dp[i + j] === Infinity) {
  15.                     continue;
  16.                 }
  17.                 if (min > dp[i + j]) { // 取最小
  18.                     min = dp[i + j];
  19.                 }
  20.             }
  21.             dp[i] = min + 1;
  22.         }
  23.     }
  25.     return dp[0];
  26. };

32. 最长有效括号

做过最难的动态规划，但也是典型的动态规划，并不超纲。
image.png

  1. var longestValidParentheses = function(s) {
  2.     let n = s.length;
  3.     if (n <= 1) {
  4.         return 0;
  5.     }
  6.     if (n === 2) {
  7.         return s === '()' ? 2 : 0;
  8.     }
  10.     let dp = new Array(n).fill(0);
  12.     for (let i = 0; i < n; i++) {
  13.         let cur = s[i];
  14.         if (cur === '(') {
  15.             dp[i] = 0;
  16.         } else {
  17.             if (s[i - 1] === '(') {
  18.                 dp[i] = 2 + ((i - 2 >= 0) ? dp[i - 2] : 0);
  19.             } else {
  20.                 if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] === '(') {
  21.                     dp[i] = 2 + dp[i - 1] + ((i - dp[i - 1] - 2 >= 0) ? dp[i - dp[i - 1] - 2] : 0);
  22.                 }
  23.             }
  24.         }
  25.     }
  27.     return Math.max(...dp);
  28. };

221. 最大正方形

规律不是特别好理解：dp[i][j] 表示 以 matrix[i][j] 为 右下顶点 的正方形的最大边长。

  1. var maximalSquare = function(matrix) { // 这动态规划好厉害
  2.     let rows = matrix.length;
  3.     let cols = matrix[0].length;
  5.     const dp = new Array(rows).fill(0).map(() => new Array(cols).fill(0));
  6.     let max = 0;
  8.     for (let row = 0; row < rows; row++) {
  9.         for (let col = 0; col < cols; col++) {
  10.             if (matrix[row][col] === '1') { // 更简洁的写法：只有为1才会被操作
  11.                 if (row === 0 || col === 0) { // 边上元素单独标记
  12.                     dp[row][col] = matrix[row][col] === '1' ? 1: 0;
  13.                 } else {
  14.                     dp[row][col] = Math.min(dp[row - 1][col - 1], dp[row - 1][col], dp[row][col - 1]) + 1;
  15.                 }
  16.                 if (max < dp[row][col]) {
  17.                     max = dp[row][col];
  18.                 }
  19.             }
  20.         }
  21.     }
  23.     return max * max;
  24. };

91. 解码方法

  1. var numDecodings = function(s) { // 动态规划，没有要求具体的例子，只是要数目
  2.     let n = s.length;
  3.     if (n === 0) {
  4.         return 0;
  5.     }
  7.     let dp = new Array(n + 1).fill(0);
  8.     dp[0] = 1;
  10.     for (let i = 1; i < n + 1; i++) {
  11.         if (s[i - 1] !== '0') {
  12.             dp[i] = dp[i - 1];
  13.         }
  15.         let cur = s.slice(i - 2, i);
  16.         if (Number(cur) <= 26 && (s[i - 2] !== '0') && i >= 2) {
  17.             dp[i] += dp[i - 2]
  18.         }
  19.     }
  21.     return dp[n];
  22. };

上台阶问题

62. 不同路径

  1. var uniquePaths = function(m, n) {
  2.     if (m === 1 || n === 1) {
  3.         return 1;
  4.     }
  6.     let dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
  8.     for (let row = m - 1; row >= 0; row--) {
  9.         for (let col = n - 1; col >= 0; col--) {
  10.             if (row === (m - 1) || col === (n - 1)) {
  11.                 dp[row][col] = 1;
  12.                 continue;
  13.             }
  15.             dp[row][col] = dp[row + 1][col] + dp[row][col + 1];
  16.         }
  17.     }
  19.     return dp[0][0];
  20. };

63. 不同路径 II

稍微比62考虑情况多一点

  1. var uniquePathsWithObstacles = function(obstacleGrid) {
  2.     let m = obstacleGrid.length;
  3.     let n = obstacleGrid[0].length;
  5.     if (m === 1 || n === 1) {
  6.         let tmp = obstacleGrid.flat();
  7.         if (tmp.includes(1)) {
  8.             return 0;
  9.         }
  10.         return 1;
  11.     }
  13.     let dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
  15.     for (let row = m - 1; row >= 0; row--) {
  16.         for (let col = n - 1; col >= 0; col--) {
  17.             if (obstacleGrid[row][col] === 1) {
  18.                 dp[row][col] = 0
  19.                 continue;
  20.             }
  22.             if ((row === m - 1) && (col === n - 1)) {
  23.                 dp[row][col] = 1;
  24.                 continue;
  25.             }
  27.             if (row + 1 >= m) {
  28.                 dp[row][col] = dp[row][col + 1];
  29.             } else if (col + 1 >= n) {
  30.                 dp[row][col] = dp[row + 1][col];
  31.             } else {
  32.                 dp[row][col] = dp[row + 1][col] + dp[row][col + 1];
  33.             }
  34.         }
  35.     }
  37.     return dp[0][0];
  39. };

45. 跳跃游戏 II

  1. var jump = function(nums) {
  2.     let n = nums.length;
  4.     let dp = new Array(n).fill(Infinity);
  5.     dp[n - 1] = 0; // 边界条件写明白
  7.     for (let i = n - 2; i >= 0; i--) {
  8.         let cur = nums[i];
  9.         if (cur === 0) {
  10.             dp[i] = Infinity;
  11.         } else {
  12.             let min = Infinity;
  13.             for (let j = 1; (j <= cur && j < n); j++) { // 递归算步伐
  14.                 if (dp[i + j] === Infinity) {
  15.                     continue;
  16.                 }
  17.                 if (min > dp[i + j]) { // 取最小
  18.                     min = dp[i + j];
  19.                 }
  20.             }
  21.             dp[i] = min + 1;
  22.         }
  23.     }
  25.     return dp[0];
  26. };