Skip to content

动态规划深入

学习动态规划范式:最优子结构、重叠子问题、制表法和记忆化。

你将学到

  • 最优子结构和重叠子问题
  • 自顶向下记忆化与自底向上制表法
  • 状态设计和转移方程
  • 滚动数组的空间优化

概念讲解

动态规划深入

动态规划(DP)通过将问题分解为重叠子问题并存储结果以避免重复计算来求解。必须满足两个性质:最优子结构(最优解包含子问题的最优解)和重叠子问题(相同子问题反复出现)。

自顶向下与自底向上

自顶向下(记忆化)从原问题出发向下递归,缓存结果。写起来自然但使用递归(有栈风险)。自底向上(制表法)从最小子问题开始填充表格。它是迭代的,因无递归开销通常更快。

状态设计

DP 最难的部分是定义状态——什么信息能刻画一个子问题。背包问题中,状态是(物品索引,剩余容量)。编辑距离中,状态是(字符串 A 的位置,字符串 B 的位置)。好的状态设计使转移自然。

转移方程

转移表达如何从较小解构建更大解。LCS:dp[i][j] = dp[i-1][j-1] + 1 若 A[i]=B[j],否则 max(dp[i-1][j], dp[i][j-1])。写转移是 DP 的核心。

空间优化

如果 dp[i] 只依赖 dp[i-1],可使用大小为 2 的滚动数组替代完整表格,将空间从 O(n^2) 降至 O(n)。

示例代码

              // Edit distance (Levenshtein) - bottom-up DP
function editDistance(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i-1] === b[j-1]) dp[i][j] = dp[i-1][j-1];
      else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
    }
  }
  return dp[m][n];
}
// 0/1 Knapsack with rolling array
function knapsack(wt, val, cap) {
  let prev = new Array(cap+1).fill(0);
  for (let i = 0; i < wt.length; i++) {
    const curr = new Array(cap+1).fill(0);
    for (let w = 0; w <= cap; w++) {
      curr[w] = prev[w];
      if (wt[i] <= w) curr[w] = Math.max(curr[w], prev[w-wt[i]] + val[i]);
    }
    prev = curr;
  }
  return prev[cap];
}
console.log('Edit distance:', editDistance('kitten', 'sitting'));
console.log('Knapsack:', knapsack([2,3,4,5], [3,4,5,6], 8));
            

编辑距离填充二维表,dp[i][j] 是将 a[:i] 转为 b[:j] 的成本。背包使用滚动数组——只需前一行,内存减半。

动手试一试

  • Code Diff

    比较递归与动态规划解法,观察记忆化如何将指数时间变为多项式时间。

常见错误

错误写法

DP 方向错误——以使用未初始化值的顺序填充表格。

正确做法

确保每个单元格的依赖在它之前填充。自底向上时,按子问题大小递增顺序迭代。

错误写法

未识别问题为 DP。

正确做法

如果问题要求最佳方式或方式数且有重叠子问题,很可能是 DP。

查阅不认识的术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误