动态规划深入
学习动态规划范式:最优子结构、重叠子问题、制表法和记忆化。
你将学到
- 最优子结构和重叠子问题
- 自顶向下记忆化与自底向上制表法
- 状态设计和转移方程
- 滚动数组的空间优化
概念讲解
动态规划深入
动态规划(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 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。