1. 递归与动态规划并不对立
先掌握递归契约。动态规划用状态表示子问题,并保存结果,避免重复计算;可以自顶向下记忆化,也可以自底向上填表。计数、可行性和最优化问题都可能适用,并不限于二维或三维问题。
写代码前依次回答:状态准确表示什么?最后一步有哪些互斥选择?最小情况如何初始化?依赖哪些已算出的状态?最终答案在哪里?最后再考虑空间压缩。
本篇输入遵守题目契约,不修改输入。整数及所有中间结果须在 Number 安全整数范围内,数组规模须在可分配范围内;示例不处理任意外部输入。
2. 爬楼梯:重复子问题与记忆化
每次上 1 或 2 阶。定义 ways(i) 为到达第 i 阶的走法数,约定 ways(0) = 1,表示不走这一种空方案。最后一步来自第 i - 1 或 i - 2 阶,两类不重叠,因此相加。这是计数递推,不必称为“最优”子结构。
朴素递归会反复算相同的 ways(i),时间呈指数增长。下面只让每个状态计算一次;缓存放在外层,所有子调用共享它,不会每次递归新建缓存。
function climbMemo(n) {
const memo = new Map([[0, 1], [1, 1]]);
function ways(i) {
if (memo.has(i)) return memo.get(i);
memo.set(i, ways(i - 1) + ways(i - 2));
return memo.get(i);
}
return ways(n);
}约定 n 为非负整数且答案安全。时间为 O(n),缓存与调用栈各为 O(n);只用于小规模教学,深递归可能超过调用栈。
如果从小到大计算,就可以只保存前两个状态:
function climbStairs(n) {
let previous = 1;
let current = 1;
for (let i = 2; i <= n; i++) {
[previous, current] = [current, previous + current];
}
return current;
}时间为 O(n),辅助空间为 O(1)。例如 n = 3 时得到 3,n = 0 时返回约定的空方案数 1。斐波那契使用相似转移,但初始值是 F(0) = 0、F(1) = 1,不要混用两题的边界。
3. 打家劫舍:选与不选
输入为非负金额数组,相邻房屋不能同时选。定义 dp[i] 为前 i 间房可获得的最大金额:不选最后一间是 dp[i - 1];选它则必须跳过前一间,是 dp[i - 2] + nums[i - 1]。两者取较大值。
function rob(nums) {
let twoBack = 0;
let oneBack = 0;
for (const value of nums) {
const current = Math.max(oneBack, twoBack + value);
twoBack = oneBack;
oneBack = current;
}
return oneBack;
}空数组返回 0。循环前两个变量分别是前两个阶段的最优值;先算新值再移动,避免覆盖依赖。时间为 O(n),辅助空间为 O(1)。追问:为什么“每次选择当前金额最大的房屋”不能保证全局最优?用 [2, 3, 2] 检查。
4. 有障碍网格:初始化也是状态的一部分
矩形网格只含 0 和 1,1 表示障碍;只允许向右或向下移动。空网格返回 0。二维状态本应表示到达某格的路径数;压缩后,更新前的 dp[col] 是上方,更新后的 dp[col - 1] 是左方。
function uniquePathsWithObstacles(grid) {
if (grid.length === 0 || grid[0].length === 0) return 0;
const dp = new Array(grid[0].length).fill(0);
dp[0] = 1;
for (const row of grid) {
for (let col = 0; col < row.length; col++) {
if (row[col] === 1) dp[col] = 0;
else if (col > 0) dp[col] += dp[col - 1];
}
}
return dp[dp.length - 1];
}遇到障碍必须清零,不能保留上行的路径数。起点有障碍时,初始的 1 也会被清零。时间为 O(mn),辅助空间为 O(n),不修改网格。
手推 [[0,0,0],[0,1,0],[0,0,0]],每行结束的状态依次为 [1,1,1]、[1,0,1]、[1,1,2]。
5. 后续题型分工
原笔记中的背包移入背包专题,连续与非连续递增移入序列专题。公共子串、礼物最大价值、单词拆分等保留在动态规划练习专题,不重复维护同一套原理。
“连续子数组和为某个数的倍数”更自然的入口是前缀和余数:相同余数之差能被除数整除,保存最早位置才能检验长度至少为 2。除数为零时要按原题契约单独处理,不能直接取模。参见前缀和。
6. 验证与闭卷练习
运行 node --test tests/algorithm-strategies-examples.test.mjs,测试直接执行文档代码。先独立手推楼梯边界、空金额数组、障碍在起点/终点/第一行,再运行测试。
闭卷时先写状态定义再写代码;将网格从“路径条数”改为“最大价值”时,说明为何加法合并变成取最大值。隔至少 3 天重做一题,记录是否需要提示。
评论
正在加载评论…