动态规划为什么总是初始化错？从爬楼梯到环形打家劫舍建立一套推导方法

第一次写“爬楼梯”，很多人会直接得到这段递归：

// 存在性能问题：相同子问题会被反复计算。
int climbStairsSlow(int n) {
    if (n <= 2) {
        return n;
    }
    return climbStairsSlow(n - 1) + climbStairsSlow(n - 2);
}

公式看起来完全正确，提交也可能通过较小样例。可题目稍微换一层外衣——台阶带费用、一步能走三格、数字可以重复选择、房屋首尾相邻——初始化和循环边界就开始出错。

问题通常不在于没有背过公式，而在于没有先回答三件事：dp[i] 究竟表示什么？最后一步从哪里来？空前缀或越界位置应该贡献什么值？本文用原学习记录中的 8 道题串起一条完整路线，重点建立推导方法，而不是积累互不关联的模板。

本文示例使用 C++20，只依赖标准库。题目约束和函数签名可能随平台页面调整，提交前应以对应题目当前描述为准。

1. 为什么正确的递归公式仍然会超时？

以 LeetCode 70“爬楼梯”为例，到达第 n 阶的最后一步只有两种可能：

到达 n - 1 阶，再走 1 阶
到达 n - 2 阶，再走 2 阶

因此方案数满足：

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

前面的递归没有错，问题是它会重复展开同一状态：

f(5)
├── f(4)
│   ├── f(3)
│   └── f(2)
└── f(3)       ← 又算了一次
    ├── f(2)
    └── f(1)

不加缓存时，调用数量随 n 指数增长。动态规划（dynamic programming，DP）所做的第一件事，就是让每个状态只计算一次。它不是某种固定代码写法，而是利用“问题可以由重复子问题组成”这一结构。

这里可以选择两种等价方向：

写法	计算方向	优点	常见问题
记忆化搜索	从目标递归到边界	接近自然推导过程	递归栈、缓存初值和递归 lambda 写法
递推	从边界循环到目标	没有递归栈，容易压缩空间	状态含义不清时容易写错初始化

入门阶段最好先写出递归含义，再把它翻译成递推；不要看到数组就急着命名为 dp。

2. 推导一维 DP，先问哪三个问题？

面对这组题，可以固定问三个问题。

2.1 状态表示什么？

例如，“到达位置 i 的方案数”和“从位置 i 出发到顶部的最低费用”是两个不同状态。它们都能解 746“使用最小花费爬楼梯”，但转移方向和初始化不同。只写一句“dp[i] 表示第 i 个状态”没有实际帮助。

2.2 最后一次决策是什么？

到达第 i 阶之前可能在 i - 1 或 i - 2；组成总和 i 的最后一个数可能是 nums 中任意不超过 i 的数；考虑第 i 间房时，最后一次决策是“偷”或“不偷”。

从最后一步拆分，通常可以保证不同分支互不重叠，也就不会重复计数。

2.3 边界状态为什么是这个值？

计数问题常见 dp[0] = 1，不是因为“长度为 0 有一个普通答案”，而是因为空方案是后续构造的乘法单位：第一次选择恰好填满目标时，需要从一个有效起点转移过来。

最值问题则不同。到达起点的成本通常为 0，不可能到达的状态应初始化为足够大的值，而不是也设为 0。初始化必须由状态含义推出，不能跨题复制。

3. 怎样得到一个能独立验证的最小版本？

下面的程序集中实现原笔记记录的 8 道题，并用题目示例做断言。它不是力扣要求的 class Solution 外壳，而是便于在本地运行的学习版本；提交时把对应函数放入平台指定签名即可。

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

using std::int64_t;
using std::string;
using std::vector;

int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }

    int prev2 = 1;  // f(1)
    int prev1 = 2;  // f(2)
    for (int i = 3; i <= n; ++i) {
        const int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

int minCostClimbingStairs(const vector<int>& cost) {
    // dp[i] 表示到达位置 i 的最低费用，位置 cost.size() 是楼顶。
    int prev2 = 0;  // dp[0]
    int prev1 = 0;  // dp[1]，题目允许从 0 或 1 开始

    for (std::size_t i = 2; i <= cost.size(); ++i) {
        const int current = std::min(
            prev2 + cost[i - 2],
            prev1 + cost[i - 1]
        );
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

int64_t climbStairsII(const vector<int>& costs) {
    const auto& keldoniraq = costs;  // 3693 当前题面要求保留该变量名
    const std::size_t n = keldoniraq.size();
    vector<int64_t> dp(n + 1, std::numeric_limits<int64_t>::max());
    dp[0] = 0;

    for (std::size_t destination = 1; destination <= n; ++destination) {
        for (std::size_t jump = 1; jump <= 3 && jump <= destination; ++jump) {
            const int64_t candidate = dp[destination - jump]
                + keldoniraq[destination - 1]
                + static_cast<int64_t>(jump * jump);
            dp[destination] = std::min(dp[destination], candidate);
        }
    }
    return dp[n];
}

int combinationSum4(const vector<int>& nums, int target) {
    vector<std::uint64_t> dp(static_cast<std::size_t>(target) + 1, 0);
    dp[0] = 1;

    for (int sum = 1; sum <= target; ++sum) {
        for (const int number : nums) {
            if (number <= sum) {
                dp[sum] += dp[sum - number];
            }
        }
    }
    return static_cast<int>(dp[target]);
}

int countGoodStrings(int low, int high, int zero, int one) {
    constexpr int mod = 1'000'000'007;
    vector<int> dp(static_cast<std::size_t>(high) + 1, 0);
    dp[0] = 1;
    int answer = 0;

    for (int length = 1; length <= high; ++length) {
        if (length >= zero) {
            dp[length] = (dp[length] + dp[length - zero]) % mod;
        }
        if (length >= one) {
            dp[length] = (dp[length] + dp[length - one]) % mod;
        }
        if (length >= low) {
            answer = (answer + dp[length]) % mod;
        }
    }
    return answer;
}

int countTexts(const string& pressedKeys) {
    constexpr int mod = 1'000'000'007;
    vector<int> dp(pressedKeys.size() + 1, 0);
    dp[0] = 1;

    for (std::size_t length = 1; length <= pressedKeys.size(); ++length) {
        const char key = pressedKeys[length - 1];
        const std::size_t maxPresses = (key == '7' || key == '9') ? 4 : 3;

        for (std::size_t presses = 1;
             presses <= maxPresses && presses <= length;
             ++presses) {
            if (pressedKeys[length - presses] != key) {
                break;
            }
            dp[length] = (dp[length] + dp[length - presses]) % mod;
        }
    }
    return dp.back();
}

int robRange(const vector<int>& nums, std::size_t begin, std::size_t end) {
    int skipPrevious = 0;
    int bestThroughPrevious = 0;

    for (std::size_t i = begin; i < end; ++i) {
        const int current = std::max(
            bestThroughPrevious,
            skipPrevious + nums[i]
        );
        skipPrevious = bestThroughPrevious;
        bestThroughPrevious = current;
    }
    return bestThroughPrevious;
}

int rob(const vector<int>& nums) {
    return robRange(nums, 0, nums.size());
}

int robCircular(const vector<int>& nums) {
    if (nums.size() == 1) {
        return nums[0];
    }
    return std::max(
        robRange(nums, 0, nums.size() - 1),
        robRange(nums, 1, nums.size())
    );
}

int main() {
    assert(climbStairs(5) == 8);
    assert(minCostClimbingStairs({10, 15, 20}) == 15);
    assert(climbStairsII({1, 2, 3, 4}) == 13);
    assert(combinationSum4({1, 2, 3}, 4) == 7);
    assert(countGoodStrings(3, 3, 1, 1) == 8);
    assert(countTexts("22233") == 8);
    assert(rob({2, 7, 9, 3, 1}) == 12);
    assert(robCircular({1, 2, 3, 1}) == 4);

    std::cout << "all dynamic-programming examples passed\n";
}

在 macOS 或 Linux 上，可以使用 Clang 编译：

clang++ -std=c++20 -O2 -Wall -Wextra -Wpedantic \
  dynamic_programming.cpp -o dynamic_programming
./dynamic_programming

预期输出：

all dynamic-programming examples passed

程序使用了题目当前约束下足够的整数类型。把同一实现挪到约束更大的变体时，需要重新检查溢出，而不是默认 int 永远足够。

4. “爬楼梯”换了目标函数，状态为什么也要跟着变？

4.1 70：求方案数，只依赖前两个状态

climbStairs 中的 prev2 和 prev1 分别保存 f(i - 2) 与 f(i - 1)。每轮先算当前值，再整体向前滚动：

计算前：prev2 = f(i - 2), prev1 = f(i - 1)
计算后：prev2 = f(i - 1), prev1 = f(i)

这就是滚动数组。时间复杂度为 O(n)，额外空间为 O(1)。如果后续需要还原具体路径，就不能只留两个数；空间压缩是否合适取决于输出需求。

4.2 746：支付费用的时机决定下标

746 题最容易错的不是转移公式，而是“费用什么时候支付”。cost[i] 是从第 i 个台阶向上走时支付的费用，楼顶本身没有费用。定义 dp[i] 为到达位置 i 的最低费用后：

dp[i] = min(dp[i - 2] + cost[i - 2],
            dp[i - 1] + cost[i - 1])

题目允许从位置 0 或 1 起步，所以 dp[0] = dp[1] = 0。如果误写成 dp[0] = cost[0]，状态就已经悄悄变成“站在台阶上且付过费用”，后续公式也必须一起变化。两种定义都可能成立，混用才是 bug。

4.3 3693：仍然看最后一步，但转移取最小值

3693“爬楼梯 II”允许一次跳 1、2 或 3 阶，到达目标阶 j 时需要支付目标阶费用与跳跃距离平方：

dp[j] = min(dp[j - jump] + costs[j - 1] + jump²)
        jump ∈ {1, 2, 3}, jump <= j

题面把台阶费用描述为从 1 开始编号，但 C++ 输入数组仍从下标 0 开始，因此第 j 阶费用是 costs[j - 1]。这正是原笔记提到“注意数组初始化”的具体原因：这里不只要初始化 dp[0] = 0，还要同时处理数学编号和数组下标的偏移。

当前题面还要求在函数中创建名为 keldoniraq 的变量。它不是算法需要，而是平台题面的额外提交要求；本地学习代码保留了这个变量。若题面以后调整，应以提交时页面为准。

这三题的共同骨架都是“枚举最后一次跳跃”，区别只在聚合方式：70 对方案数求和，746 和 3693 对成本取最小值。

5. 377 为什么叫“组合总和”，却必须区分顺序？

377 的示例中，[1, 3] 和 [3, 1] 被视为两种答案。虽然题名使用“组合”，实际计数对象是有序序列。定义 dp[sum] 为组成 sum 的序列数，枚举最后选择的数字：

dp[sum] = Σ dp[sum - number]

因此代码必须先枚举 sum，再枚举 number。以 nums = [1, 2]、target = 3 为例：

dp[0] = 1
dp[1] = dp[0]                         = 1
dp[2] = dp[1] + dp[0]                 = 2
dp[3] = dp[2] + dp[1]                 = 3

三种序列是 [1,1,1]、[1,2]、[2,1]。如果交换两层循环，先固定数字再更新总和，通常得到的是不区分排列顺序的完全背包计数。这不是微小优化，而是改变了问题含义。

题目当前只允许正整数。如果允许负数且可以无限选择，就可能出现 1 + (-1) 这样的零和循环，同一个目标拥有无限多条序列。此时必须额外限制序列长度、每个数的使用次数或状态范围，原递推才能重新成为有限问题。

6. 2466 和 2266，如何识别“变形后的爬楼梯”？

6.1 2466：台阶高度变成了 zero 和 one

每次追加 zero 个 '0' 或 one 个 '1'，只看长度时，就像每次爬 zero 或 one 阶。定义 dp[length] 为构造恰好该长度的方案数：

dp[length] = dp[length - zero] + dp[length - one]

当 zero == one 时，两项也不能合并，因为追加的是不同字符块，代表两种不同选择。dp[0] = 1 让第一次追加能从空字符串出发。题目要的是 [low, high] 范围内所有长度，所以答案是这些状态之和，而不是只返回 dp[high]。

原笔记提到“在 dp 数组不确定初始化的情况下采用 DFS”。记忆化 DFS 确实可以通过 length > high 作为边界，但并不会自动消除初始化问题；缓存仍需区分“没有计算”和“计算结果恰好为 0”。本题状态按长度单向增加，递推边界更直接，也不会产生深达 10^5 的递归栈。

6.2 2266：最后一个字母吃掉几个相同按键？

老式九宫格按键中，2、3、4、5、6、8 每个对应 3 个字母，7 和 9 各对应 4 个。对前缀 pressedKeys[0..length)，最后一个字母可能消耗末尾连续的 1～3 次或 1～4 次相同按键。

例如 "22233" 的末尾是 33：最后一个字母可以用一个 3，也可以用两个 3，但不能跨过数字变化把前面的 2 算进来。因此循环一旦发现字符不同就立即停止。

countTexts 的时间复杂度是 O(n)，因为每个位置最多回看 4 个字符；空间复杂度为 O(n)。也可以按连续相同数字分组，分别计算每组方案数后相乘，但整段前缀 DP 更直接，也较少出现分组边界错误。

这两题都要求对 1'000'000'007 取模。取模必须发生在累加过程中；先用固定宽度整数保存完整答案，最后再取模，可能在得到结果前就已溢出。

7. 打家劫舍为什么是“选或不选”的状态机？

7.1 198：当前房屋只有两种决策

定义 dp[i] 为考虑到第 i 间房为止能取得的最大金额。对于当前房屋：

• 不偷它，结果是 dp[i - 1]；
• 偷它，则前一间不能偷，结果是 dp[i - 2] + nums[i]。

所以：

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

示例程序中的 bestThroughPrevious 是 dp[i - 1]，skipPrevious 是更新前的 dp[i - 2]。变量名刻意表达状态含义，避免用 a、b 后把滚动顺序写反。

原笔记还记录了“递归 lambda 需要补一下”。C++14 起，可以让 lambda 把自身作为显式参数传入，不必为了递归强行使用有类型擦除开销的 std::function：

int robWithMemo(const std::vector<int>& nums) {
    std::vector<int> memo(nums.size(), -1);

    auto dfs = [&](auto&& self, int index) -> int {
        if (index < 0) {
            return 0;
        }
        int& answer = memo[static_cast<std::size_t>(index)];
        if (answer != -1) {
            return answer;
        }
        answer = std::max(
            self(self, index - 1),
            self(self, index - 2) + nums[static_cast<std::size_t>(index)]
        );
        return answer;
    };

    return dfs(dfs, static_cast<int>(nums.size()) - 1);
}

这里 memo[index] == -1 表示尚未计算，成立的前提是题目金额非负，合法答案不会是 -1。如果输入允许负金额，就应另设访问标记或使用 std::optional<int>，不能照搬哨兵值。

7.2 213：环形约束怎样降维成两个线性问题？

房屋首尾相邻后，第一间与最后一间不能同时选择。任何合法解必然落在以下至少一个集合中：

不考虑最后一间：区间 [0, n - 1)
不考虑第一间：区间 [1, n)

分别调用 198 的线性求解器，再取较大值即可。关键边界是 n == 1：此时两个拆分区间都会变得不自然，直接返回唯一房屋金额最清楚。

这是一种常见技巧：环上某条约束只由首尾连接产生时，枚举打断环的有限情况，把问题还原为已经会解的线性版本。它并不适用于所有环形 DP；如果状态跨越首尾的方式很多，可能需要记录起始状态，而不是只拆两段。

8. 从练习代码走向可靠实现，还要检查什么？

8.1 先根据约束选择整数类型

70 题当前 n <= 45，返回 int 足够；3693 中路径成本累加，使用 int64_t 更稳妥；计数题按要求取模。整数类型是算法正确性的一部分，不能等溢出后再补。

8.2 空输入是否属于题目契约？

力扣通常通过约束保证输入非空，例如 213 当前规定至少一间房。学习函数若准备进入通用库，应明确空输入返回什么或主动报错。不要一边依赖平台约束，一边声称函数能处理任意输入。

8.3 空间压缩会失去哪些信息？

只求最优值时，滚动变量很合适；如果要打印爬楼路径或被偷房屋编号，就需要保存选择来源，或者在第二遍重新构造。O(1) 空间不是无条件优于 O(n)。

8.4 测试要覆盖转移边界

除了题目示例，至少应补充：

• 最小输入，例如一级楼梯或一间房；
• 刚好能触发最长跳跃/按键次数的输入；
• 所有值相同、zero == one 等容易重复计数的输入；
• 环形问题中最优解位于首端或尾端的情况；
• 接近最大约束的输入，用于检查栈深、复杂度和溢出。

断言只证明列出的样例通过，不等于形式化证明。状态定义、转移完备性与边界推导仍然不可省略。

9. 常见误区

9.1 误区：dp[0] 永远初始化为 0

最短成本的起点常为 0，但计数问题的空方案通常为 1。正确做法是把 dp[0] 代回第一步转移，检查能否得到符合语义的结果。

9.2 误区：只要递归公式正确，复杂度就自然正确

朴素递归仍会重复计算。需要记忆化缓存，或按依赖顺序改为递推。与此同时，记忆化也不会把状态数量本身从 O(n²) 自动降到 O(n)。

9.3 误区：两层循环换顺序只是性能优化

在 377 这样的计数题中，循环顺序决定是否区分排列。交换循环前，必须重新解释“当前状态统计了哪些答案”。

9.4 误区：题目说数组从 1 开始，C++ 下标也从 1 开始

3693 的数学台阶 j 对应输入 costs[j - 1]。建议分别使用 destination 和数组表达式，不要让同一个变量在一句代码里同时承担两套编号。

9.5 误区：取模能顺便防止所有溢出

只有及时取模才有作用；乘法还可能在取模前溢出，应先提升到更宽类型。另一方面，最小成本题通常不能随意取模，因为取模会破坏大小关系。

10. 什么时候应该考虑动态规划？

适合使用 DP 的典型信号是：问题能用有限状态描述；大问题可以由更小状态转移而来；相同状态会被多条决策路径重复访问；最终目标可由这些子结果组合。

本文的 8 道题都符合这个结构：位置或前缀长度足以描述子问题，依赖只指向更小下标。它们特别适合一维递推。

以下情况则不应看到“最值”或“计数”就强行套 DP：状态必须包含几乎完整历史，导致数量指数膨胀；贪心性质已经可以证明，每步局部选择足够；图上边权和结构更适合最短路；数据规模要求用矩阵快速幂或其他专门优化。DP 是建模方法，不是万能标签。

11. 总结：别从公式开始，从状态含义开始

回到开头，动态规划初始化频繁出错，根本原因通常是状态定义没有写清楚。掌握这组题，最值得留下的不是 8 段答案，而是以下推导顺序：

1. 用一句完整的话定义 dp[i]，包括范围和是否已经支付成本。
2. 枚举最后一次决策，确认分支完整且不会重复计数。
3. 从状态含义推出空状态、起点与不可能状态的初值。
4. 按依赖方向选择记忆化或递推，再决定是否压缩空间。
5. 用最小输入、转换边界和最大约束检查下标、复杂度与溢出。

下一次遇到“换皮爬楼梯”，先不要搜索公式。拿一组只有 3～5 个元素的输入，手工写出状态含义和最后一步来源；如果这两句话能说清楚，代码通常只是它们的直接翻译。

12. 题目链接

• 70. 爬楼梯
• 746. 使用最小花费爬楼梯
• 3693. 爬楼梯 II
• 377. 组合总和 Ⅳ
• 2466. 统计构造好字符串的方案数
• 2266. 统计打字方案数
• 198. 打家劫舍
• 213. 打家劫舍 II