算法：动态规划

发表于 | 分类于

动态规划

核心

  • 记住已经解决过的子问题的解

原理

  • 最优子结构：一个问题的解结构包含其子问题的最优解，用子问题的最优解来构造原问题的最优解
  • 重叠子问题：递归算法反复求解相同的子问题，使用数组来保存子问题的解

求解

  • 找到状态转移方程，进行自底向上的求解
  • 步骤：1 定义子问题 2 实现要反复执行来解决子问题的部分 3 识别并求解出基线条件

最长回文子串

思路：
从中间往两边去

  1. 确定dp[i][j]是否是回文数，只需要dp[i+1][j-1]是回文并且s[i]==s[j]即可
  2. 长度为0和1的要做特殊处理，j-i<2的情况
  3. i从大到小遍历，j从小到大遍历
  4. 状态转移方程：dp[i][j] = s[i] == s[j] && ( dp[i+1][j-1] || j - i < 2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var longestPalindrome = function(s) {
  let ans = '';
  let n = s.length;
  let dp = Array.from(new Array(n),() => new Array().fill());
  for (let i=n-1; i>=0; i--) {
    for(let j = i;j < n;j++) {
      dp[i][j] = s[i] === s[j] && (j-i < 2 || dp[i+1][j-1])
      if(dp[i][j] && j-i+1 > ans.length) {
        ans = s.substr(i, j-i+1);
      }
    }
    
  }
  return ans;
}

最小路径和

  • 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
  • input
    [
    [1,3,1],
    [1,5,1],
    [4,2,1]
    ]
  • output 7(1-3-1-1-1)

思路：

  1. 状态转移方程：grid[i][j] = grid[i][j] + Math.min(grid[i-1][j] + grid[i][j-1])
  2. 考虑i和j是0的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var miniPathSum = function(grid) {
  const m = grid.length;
  const n = grid[0].length;
  for(let i = 0; i < m ; i++) {
    for(let j = 0; j < n; j++) {
      if(i === 0 && j !== 0) {
        grid[i][j] += grid[i][j-1];
      }
      else if(i !== 0 && j === 0) {
        grid[i][j] += grid[i-1][j];
      }
      else if(i !== 0 && j !== 0) {
        grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
      }
    }
  }
  return grid[m-1][n-1];
}

打家劫舍

  • 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
  • [1,2,3,1] => 4(=1+3)
  • [2,7,9,3,1] => 12(=2+9+1)

思路：

  1. 状态转移方程：第k次 = 前面k个屋子可以抢到的最大数 + 这次的数
  2. f(k) = max(f(k-2) + Ak, f(k-1))
1
2
3
4
5
6
7
8
9
10
11
12
13
var rob = function(nums) {
  const n = nums.length;
  if (n < 2) {
    return nums[0] ? nums[0] : 0; 
  }
  let current = [];
  current[0] = nums[0];
  current[1] = Math.max(nums[0], nums[1]);
  for(let i=2;i<n;i++) {
    current[i] = Math.max(current[i-2] + nums[i], current[i-1]);
  }
  return current[n-1];
}