算法——动态规划

发表于 分类于 ， ， 阅读次数：

动态规划（Dynamic Programming，DP）与递归常常可以一起使用。核心思想是：将大问题拆成小问题，先解决小问题，再根据小问题的解推导出大问题的解。关键是要找到状态定义和状态转移方程。

递归

  递归是 DP 的基础——一个问题可以拆成若干个结构相同的子问题。比如爬楼梯：到第 n 级台阶，要么从 n-1 跨一步上来，要么从 n-2 跨两步上来。所以：

1
f(n) = f(n-1) + f(n-2)

  用递归直接写：

1
2
3
4
function climb(n) {
  if (n <= 2) return n;
  return climb(n - 1) + climb(n - 2);
}

  但有大量重复计算——climb(5) 会计算 climb(3) 两次。DP 就是来消除这些重复的。

初始状态（Base Case）

  递归需要终止条件，DP 需要初始状态。找初始状态就是问：问题最小到什么程度可以直接得出答案？

  • 爬楼梯：f(1) = 1，f(2) = 2
  • 最大子序和：dp[0] = nums[0]，第一个元素的最大子序和就是它自己
  • 斐波那契：fib(0) = 0，fib(1) = 1

状态转移方程

  这是 DP 的核心——当前状态怎么从前面的状态推导过来。写好方程，代码就是照着翻译。

问题 状态定义 转移方程
爬楼梯 dp[i] 表示到第 i 阶的方法数 dp[i] = dp[i-1] + dp[i-2]
最大子序和 dp[i] 表示以 i 结尾的最大子序和 dp[i] = max(nums[i], dp[i-1] + nums[i])
斐波那契 dp[i] 表示第 i 个斐波那契数 dp[i] = dp[i-1] + dp[i-2]

爬楼梯完整实现

1
2
3
4
5
6
7
8
function climbStairs(n) {
  if (n <= 2) return n;
  const dp = [0, 1, 2]; // dp[1] = 1, dp[2] = 2
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

最大子序和完整实现

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

状态压缩（空间优化）

  很多 DP 问题中，当前状态只依赖前几个状态，不需要保留整个 dp 数组，用几个变量滚动更新即可。

1
2
3
4
5
6
7
8
9
// 爬楼梯空间优化：O(n) → O(1)
function climbStairs(n) {
  if (n <= 2) return n;
  let prev = 1, curr = 2;
  for (let i = 3; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}
1
2
3
4
5
6
7
8
9
10
// 最大子序和空间优化
function maxSubArray(nums) {
  if (!nums.length) return 0;
  let prev = nums[0], max = prev;
  for (let i = 1; i < nums.length; i++) {
    prev = Math.max(nums[i], prev + nums[i]);
    max = Math.max(max, prev);
  }
  return max;
}

最优解

  DP 求的是最优子结构——如果子问题是最优的，那么组合出来的父问题也是最优的。区分 DP 和贪心：

  • 贪心：每一步选当前最优，不考虑未来
  • DP：枚举所有可能的状态，通过状态转移方程找到全局最优

  比如爬楼梯求的是「方法数」，不是最优值，严格来说属于计数型 DP。求最优值的典型问题是最大子序和。

题目

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

思路：到第 n 阶 = 到第 n-1 阶再跨 1 步 + 到第 n-2 阶再跨 2 步，即斐波那契数列。

1
2
3
4
5
6
7
8
function climbStairs(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路：对于每个位置 i，要么自己单独成子数组，要么加入前面的子数组。取较大的那个。

1
2
3
4
5
6
7
8
9
10
function maxSubArray(nums) {
  if (!nums.length) return 0;
  let prev = nums[0];
  let max = prev;
  for (let i = 1; i < nums.length; i++) {
    prev = Math.max(nums[i], prev + nums[i]);
    max = Math.max(max, prev);
  }
  return max;
}