Skip to content

1. 递归与动态规划并不对立 ​

先掌握递归契约。动态规划用状态表示子问题,并保存结果,避免重复计算;可以自顶向下记忆化,也可以自底向上填表。计数、可行性和最优化问题都可能适用,并不限于二维或三维问题。

写代码前依次回答:状态准确表示什么?最后一步有哪些互斥选择?最小情况如何初始化?依赖哪些已算出的状态?最终答案在哪里?最后再考虑空间压缩。

本篇输入遵守题目契约,不修改输入。整数及所有中间结果须在 Number 安全整数范围内,数组规模须在可分配范围内;示例不处理任意外部输入。

2. 爬楼梯:重复子问题与记忆化 ​

每次上 1 或 2 阶。定义 ways(i) 为到达第 i 阶的走法数,约定 ways(0) = 1,表示不走这一种空方案。最后一步来自第 i - 1 或 i - 2 阶,两类不重叠,因此相加。这是计数递推,不必称为“最优”子结构。

朴素递归会反复算相同的 ways(i),时间呈指数增长。下面只让每个状态计算一次;缓存放在外层,所有子调用共享它,不会每次递归新建缓存。

js
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);只用于小规模教学,深递归可能超过调用栈。

如果从小到大计算,就可以只保存前两个状态:

js
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]。两者取较大值。

js
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] 是左方。

js
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 天重做一题,记录是否需要提示。

评论

正在加载评论…