4201 字
21 分钟
用 C++ 学懂动态规划：从状态定义到 0/1 背包
2026-10-29算法C++动态规划算法入门

动态规划最难的地方，往往发生在写代码之前：数组里到底存什么？为什么能用前面的答案推出后面的答案？循环应该从左往右，还是从右往左？

这篇文章用三个问题，把这些选择背后的理由逐一讲清楚。所有完整代码都遵循 C++17，可以单独编译运行。阅读时可以先把公式翻译成一句中文，再看它如何落到数组和循环上。

一、先理解“保存答案”解决了什么#

假设每次能爬 1 级或 2 级台阶，要爬到第 n 级，一共有多少种走法？

如果用 ways(n) 表示答案，最后一步只有两种可能：从第 n - 1 级跨 1 级上来，或者从第 n - 2 级跨 2 级上来。两类走法互不重叠，于是：

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

直接照着公式递归，计算 ways(5) 时会展开 ways(4) 和 ways(3)；计算 ways(4) 时，又会算一次 ways(3)。问题规模变大后，同样的子问题会被反复计算。

动态规划把已经求出的子问题答案保存下来。它常见的两种写法是：

  • 记忆化搜索：从目标出发递归，遇到算过的状态就读取缓存。
  • 递推填表：先求最小的状态，再按依赖顺序计算更大的状态。

两者都需要明确状态和转移。本文采用递推填表，因为数组内容和执行顺序更容易观察。朴素递归有指数级的调用数量，而保存答案后，爬楼梯只需要计算 n + 1 个状态。

这里也有一个前提：状态必须留下足够的信息，使后续决策只依赖当前状态。如果问题还限制“不能连续跨两次 2 级”，单独记录所在台阶就不够，还得记录上一步是否跨了 2 级。数组维度应由这些必要信息决定。

二、把一道题拆成五个问题#

动手前，先写出下面这张表。它比套用某个代码模板更有用。

步骤必须说清楚的内容
定义状态dp 的每个下标表示什么，存储的是数量、最优值还是可行性？
推导转移当前答案能从哪些更小的状态获得？这些选择是否完整？
设置初值最小问题的答案是什么？不可达状态用什么表示？
安排遍历计算当前状态时，它依赖的状态是否已经可用？
确认答案要返回哪个位置，还是整个数组中的最大值？

对于求最优值的问题，还要检查最优子结构：固定最后一次选择后，剩余部分的最优解能否用于构造当前最优解。如果更换前面的方案会破坏后续约束，说明状态可能遗漏了信息。

复杂度也可以沿着这张表分析：先数有多少个状态，再数每个状态需要检查多少种转移。两者相乘，通常就是时间复杂度的主要部分。

三、例一：爬楼梯，理解状态与初值#

1. 定义状态和转移#

令 dp[i] 表示“恰好到达第 i 级台阶的不同走法数量”。最后一步跨 1 级或 2 级，所以：

dp[i] = dp[i - 1] + dp[i - 2]    （i >= 2）

注意这里求的是方案数量，因此把互不重叠的方案数相加。后面的最少硬币问题求的是最优值，聚合方式会换成取最小值。

2. 为什么 dp[0] = 1#

到达第 0 级，也就是原地不动，存在一种“什么都不做”的方案。它让递推保持一致：到达第 1 级的方案数是 dp[0]，正好等于 1。

如果把 dp[0] 设成 0，后面的答案会全部变成 0。初值应来自状态的含义，不能因为“数组默认是 0”就省略思考。

前几个状态如下：

台阶 i012345
dp[i]112358

计算 dp[i] 只依赖更小的下标，按 i = 1, 2, …, n 递增遍历即可；最终答案是 dp[n]。

3. 完整 C++17 代码#

stairs.cpp
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <vector>


std::int64_t climbStairs(int n) {
    // dp[n] = Fibonacci(n + 1)，有符号 64 位整数只支持到 n = 91。
    if (n < 0 || n > 91) {
        throw std::invalid_argument("n must be in [0, 91]");
    }


    std::vector<std::int64_t> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1];
        if (i >= 2) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}


int main() {
    std::cout << climbStairs(0) << '\n';   // 1
    std::cout << climbStairs(5) << '\n';   // 8
    std::cout << climbStairs(91) << '\n';  // 7540113804746346429
}

时间复杂度为 O(n)，空间复杂度为 O(n)。只保存前两个状态，还能把额外空间降到 O(1)；更新时要先用旧值算出新值，再移动这两个变量。

特别留意数字范围：第 92 级的答案是 12200160415121876738，已超过有符号 64 位整数的上限。换成 long long 并不意味着可以无限计算。更大的输入需要大整数；若题目要求取模，则应按题意在转移时取模。

四、例二：零钱兑换，处理最优值与不可达#

现在有若干种正整数面额的硬币，每种可以无限使用。给定目标金额，求凑出它所需的最少硬币数；凑不出来时返回 -1。

面额为 [1, 3, 4]、目标为 6 时，先拿最大面额会得到 4 + 1 + 1，用了 3 枚；最优方案却是 3 + 3，只用 2 枚。因此，不能默认每一步选择最大面额就能得到最优解。

1. 从最后一枚硬币推导#

令 dp[s] 表示“恰好凑出金额 s 所需的最少硬币数”。如果最后一枚面额为 c，前面必须先凑出 s - c，因此候选答案为：

dp[s - c] + 1

枚举所有满足 c <= s 的面额，在可达的候选答案中取最小值。这些候选覆盖了任意有效方案的最后一枚硬币。如果某个最优方案去掉最后一枚后，剩下的方案并非 s - c 的最优方案，就能用更少的硬币替换它，与原方案最优矛盾。

2. 初值为什么不能全设为 0#

dp[0] = 0，因为凑出金额 0 不需要硬币。其他金额一开始还不知道是否可达，不能用 0 表示，否则程序会把“没算出来”误认为“零枚硬币即可凑出”。

本例用 amount + 1 表示不可达。所有面额都是正整数，如果目标金额可达，任意方案的硬币数都不会超过 amount，因此这个哨兵值足够大。转移前仍检查来源是否可达，避免让哨兵参与有效答案计算。

3. 完整 C++17 代码#

coin_change.cpp
#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <vector>


int minCoins(const std::vector<int>& coins, int amount) {
    // 教学示例限制金额，避免不合理的内存申请，也保证哨兵加法安全。
    if (amount < 0 || amount > 1000000) {
        throw std::invalid_argument("amount must be in [0, 1000000]");
    }
    for (int coin : coins) {
        if (coin <= 0) {
            throw std::invalid_argument("coin values must be positive");
        }
    }


    const int INF = amount + 1;
    std::vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int s = 1; s <= amount; ++s) {
        for (int coin : coins) {
            if (coin <= s && dp[s - coin] != INF) {
                dp[s] = std::min(dp[s], dp[s - coin] + 1);
            }
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}


int main() {
    std::cout << minCoins({1, 3, 4}, 6) << '\n';  // 2
    std::cout << minCoins({2}, 3) << '\n';        // -1
    std::cout << minCoins({2}, 0) << '\n';        // 0
}

金额从小到大遍历。由于面额为正，s - coin < s，转移来源一定已经算完。这个状态允许重复使用硬币：求较大金额时，可以继续利用已经包含同面额硬币的较小金额状态。

以面额 [1, 3, 4] 为例，计算过程得到下面这一行：

金额 s0123456
最少枚数 dp[s]0121122

计算金额 6 时，最后一枚为 1、3、4 的候选分别是 dp[5] + 1 = 3、dp[3] + 1 = 2、dp[2] + 1 = 3。取最小值得到 2。这里枚举了最后一枚的所有可能，因此不会因为先看到面额 4 就错过更优方案。

如果换成只有面额 2，那么金额 1 一直不可达，金额 3 也无法从金额 1 转移过来。用“不可达”单独描述这些状态，算法才不会凭空构造不存在的方案。

设目标金额为 A，面额数量为 m，时间复杂度为 O(A × m)，额外空间为 O(A)。它与金额的数值有关，所以面对极大的金额，即使输入只有几个整数，也可能运行得很慢。

五、例三：0/1 背包，弄懂逆序循环#

有 n 件物品，第 i 件的重量为 w[i]，价值为 v[i]。每件最多选一次，背包容量为 W，求总重量不超过容量时的最大总价值。

“每件最多选一次”是 0/1 背包的关键约束；它决定空间压缩后的循环方向。

1. 先从二维状态理解#

令 dp[i][c] 表示“只考虑前 i 件物品，容量上限为 c 时的最大价值”。当前物品只有两种选择：

  • 不选：价值保持 dp[i - 1][c]。
  • 选一次：若放得下，价值为 dp[i - 1][c - w] + v。

因此，当 c >= w 时：

dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - w] + v)

放不下时只保留“不选”的结果。所有来源都属于上一行，因此同一件物品不会被重复使用。

没有物品时，允许什么都不选，所以 dp[0][c] = 0。这里的含义是“总重量不超过容量”，并不要求恰好装满。若题目改成“必须恰好装满”，就需要将非零容量初始化为不可达，不能直接复用全零初值。

2. 压缩成一维后，为何必须逆序#

当前行只依赖上一行，可以只保留一个数组 dp[c]。处理一件物品时，让容量从 W 递减到它的重量：

dp[c] = max(dp[c], dp[c - w] + v)

这样读取较小下标 dp[c - w] 时，它还没有在本轮被更新，代表“尚未考虑当前物品”的上一行答案。

看一个只有一件物品的反例：重量 2、价值 3、容量 4。若容量正序遍历，先把 dp[2] 更新为 3，随后计算 dp[4] 时又读取这个新值，得到 3 + 3 = 6，相当于同一件物品选了两次。

逆序时，先计算 dp[4]，此时 dp[2] 还是 0，结果只能是 3。之后才更新 dp[2]。循环方向的作用，是控制读到“上一轮状态”还是“本轮新状态”。

3. 完整 C++17 代码#

下面约定：物品数不超过 1000，容量在 0..100000，重量为正整数，价值在 0..10^9。最大价值总和不超过 10^12，用有符号 64 位整数存储。

knapsack.cpp
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <vector>


struct Item {
    int weight;
    std::int64_t value;
};


std::int64_t knapsack01(const std::vector<Item>& items, int capacity) {
    if (items.size() > 1000 || capacity < 0 || capacity > 100000) {
        throw std::invalid_argument("invalid item count or capacity");
    }
    for (const auto& item : items) {
        if (item.weight <= 0 || item.value < 0 || item.value > 1000000000LL) {
            throw std::invalid_argument("invalid weight or value");
        }
    }


    std::vector<std::int64_t> dp(capacity + 1, 0);
    for (const auto& item : items) {
        for (int c = capacity; c >= item.weight; --c) {
            dp[c] = std::max(dp[c], dp[c - item.weight] + item.value);
        }
    }
    return dp[capacity];
}


int main() {
    std::cout << knapsack01({{1, 15}, {3, 20}, {4, 30}}, 4) << '\n'; // 35
    std::cout << knapsack01({{2, 3}}, 4) << '\n';                   // 3
    std::cout << knapsack01({{2, 3}}, 0) << '\n';                   // 0
}

时间复杂度为 O(n × W)，额外空间为 O(W)。二维写法的空间是 O(n × W)；压缩只是省掉了无需保留的历史行，没有减少状态转移的总次数。

对代码中的三件物品，可以把每次处理完后的数组列出来：

已考虑的物品容量 0容量 1容量 2容量 3容量 4
无00000
重量 1，价值 15015151515
再加入重量 3，价值 20015152035
再加入重量 4，价值 30015152035

第二件物品加入时，容量 4 可以装下重量 1 和重量 3 的组合，总价值是 35。第三件物品虽然单件价值更大，但单独装入只有 30，因此不能替换原来的最优答案。容量 2 的值也是 15，因为状态只要求不超重，空余 1 单位容量完全允许。

二维版本的每一行使用独立数组，容量正序或逆序都可以；逆序要求来自“一维数组覆盖旧值”这个条件。理解这一点，才能在完全背包、滚动数组等问题中自己判断方向。

六、把三道题放在一起看#

问题状态存什么转移如何合并初值遍历依据
爬楼梯到达某级的方案数两个来源相加dp[0] = 1来源下标更小
零钱兑换凑出某金额的最少枚数可达候选取最小值0 金额为 0，其余不可达面额为正，来源金额更小
0/1 背包给定容量上限的最大价值选或不选取最大值允许空方案，全部为 0一维压缩时保留上一轮来源

写不出转移方程时，可以先问“最后一次选择是什么”。爬楼梯看最后一跨，零钱兑换看最后一枚，背包看当前物品选不选。把选择固定以后，再判断剩余部分是否正好是已经定义的子问题。

但不要只记住 min、max 和加法的外形。同样一行代码，状态解释或循环顺序不同，解决的就可能是另一道题。例如零钱问题若改成“统计方案数”，还要区分 1 + 2 与 2 + 1 是否算两种；原来求最小值的循环不能未经推导就搬过去。

七、调试时优先检查这些地方#

  1. 把状态解释写在数组旁边。 “容量不超过 c”和“恰好占用 c”含义不同，初值和最终答案也会不同。
  2. 先算最小输入。 空物品、金额 0、台阶 0、完全放不下的情况，最容易暴露初值错误。
  3. 检查不可达来源。 不要让代表不可达的极大值继续加 1；如果使用整数最大值，这还可能触发溢出。
  4. 先写清二维依赖，再压缩空间。 确认需要旧行还是新行，循环方向就有了依据。
  5. 用能区分错误模型的小例子验证。 背包用“一件物品却能放下两次”，零钱用“贪心失败”和“无法凑出”的例子，比只跑普通样例更有效。

可以分别将代码保存为对应的 .cpp 文件，再编译运行：

Terminal window
g++ -std=c++17 -Wall -Wextra -pedantic stairs.cpp -o stairs
./stairs

八、求出最优值后，怎样知道选了什么#

上面的数组记录的是数量或最优值，没有直接保存完整方案。如果还想输出零钱兑换到底用了哪些硬币，可以在更新 dp[s] 时，同时记录本次采用的面额 choice[s]。

从目标金额出发，读取 choice[s]，输出这枚硬币，再把 s 减去它的面额，如此重复直到金额变成 0。对于目标 6，若记录的选择是 3，就会沿着 6 → 3 → 0 得到两枚面额 3 的硬币。开始恢复之前，要先确认目标可达。

背包也可以保存选择，但一维压缩后历史状态已经被覆盖，不能随便沿着当前数组回溯。初学时可以保留二维表：从最后一行的目标容量往前检查，若当前最优值与上一行相同，就可以跳过当前物品；否则选取当前物品，并减去它的重量，再进入上一行。存在多个最优方案时，这种处理恢复其中一种即可。

这也解释了为什么应先确定输出要求：只求一个最优数字，滚动数组通常很合适；还要恢复具体决策，则需要保存足够的历史信息，空间优化的方案也要一起调整。

学习的下一步，可以尝试“最小路径和”“最长公共子序列”和“完全背包”。每道题都先写出那五项：状态、转移、初值、遍历顺序、答案位置。当你能解释每个下标和每次更新的含义，动态规划就会从记忆模板变成一种可以推导的解题方法。

分享文章

生成精美分享图或复制链接，与更多人分享本文。