算力手记C++ & COMPUTING SYSTEMS

CHAPTER 22 / 数据结构与算法

动态规划与解题表达：状态必须回答一句话

最少硬币和背包为什么能复用旧答案，却不能乱改循环顺序？

阅读与推演约 60 分钟练习时间另计

这一章要弄清楚

  • 用清晰语句定义状态
  • 推导转移、基础值和计算顺序
  • 区分可重复选择与只能选择一次

先备知识：测试与调试：独立定位失败 / 数组、哈希与双指针：重复工作从哪里删掉 / 二分、排序与堆：保留哪些候选 / 递归、树与图：沿着依赖和边访问

ISO C++20；macOS 或 Linux；仅标准库；示例是独立教学程序，非学习者验收。

先发现重复子问题

求凑出金额六的最少硬币，币值为一、三、四。如果枚举最后一枚硬币，就分别需要知道金额五、三、二的最优答案，再加一。递归展开时许多金额会反复出现。保存已经解决的子问题，就是动态规划的起点。它不是“见到最优就开一个数组”，而是确认大问题能由适当的较小状态组合，并且相同状态以后不需要重新求解。

给状态写一句完整定义：dp[s] 表示恰好凑出金额 s 的最少硬币数，允许每种币重复使用。这个定义同时固定了目标是恰好、优化的是数量、以及可重复使用。若改成不超过金额、统计方案数或每枚只能一次，转移和循环方向都会变化。很多 DP bug 来自代码写完后才想清 dp 究竟代表什么。

转移来自最后一步，而不是背公式

考虑最后选币 c，前一状态是 s-c，因此候选为 dp[s-c]+1。对所有可用正币值取最小。金额零用零枚，是基础值；不可达状态用一个明显大于任何可行答案的哨兵，且不要对最大整数直接加一导致溢出。因为币值正，依赖状态金额更小，可按金额递增计算。

对于币值一、三、四，dp[1]=1，dp[2]=2，dp[3]=1，dp[4]=1，dp[5]=2，dp[6]=2。贪心先拿四再拿一、一需要三枚，但三加三只要两枚，这说明局部选最大不总有全局最优保证。只有满足特定结构时才能用贪心替代完整 DP。

背包说明循环方向的含义

零一背包中，每件物品最多使用一次，dp[capacity] 表示在当前已处理物品范围内、不超过该容量能取得的最大价值。处理新物品时从大容量往小容量更新，这样读取 dp[capacity-weight] 时仍是没有使用当前物品的旧阶段结果。若从小到大，刚更新的小容量会被本轮再次读取，等于允许同一物品反复使用。

本章例子重量二和三，价值三和四，总容量四。合法最优值四，只能拿重量三那件；错误的正向零一更新可能把重量二拿两次得到六。用这个短反例，比在大表中寻找问题更快。空间压缩后阶段维度虽然不再显式储存，却仍然存在于循环顺序的语义中。

从答案扩展到方案

只保留最优数值不一定足以恢复选择。如果要解释用了哪些硬币，可保存每个金额最后选的币，再从目标反向减去；背包恢复可保存二维决策表或采用谨慎的重建策略。遇到多个相同最优方案时，提前定义任意一个、字典序最小或全部方案，不要让测试错误地要求唯一答案。

复杂度按状态数量乘每个状态的转移成本分析。金额为 A、币种 m 的硬币 DP 通常 O(A×m)，依赖数值大小，因此是伪多项式风格的复杂度，不能仅把输入硬币个数当 n。若金额可达十亿，这个数组方案即使推导正确也可能不可用，需重新利用问题结构。

用六句话完成面试说明

先复述输入约束和答案语义；给出朴素思路及重复工作；定义状态；解释转移和基础值；说明为什么计算顺序保证依赖已就绪；最后给复杂度和边界测试。先用二维或明确阶段版本得到可信解，再做滚动数组等优化。一次只压缩一种维度，保留小规模参考解进行差分测试，避免把省空间变成难以验证的状态混用。

观察 · 推演

币值 [1,3,4] 的最少枚数

dp[0]0dp[1]1dp[2]201 / 04 · PIPELINEdp[0]0dp[1]1dp[2]201 / 04 · PIPELINE
基础金额

金额 0 不需要硬币；1 和 2 只能用币 1。

1 / 4
阅读完整推演文字
  1. 基础金额

    dp[0]：0；dp[1]：1；dp[2]：2

    金额 0 不需要硬币；1 和 2 只能用币 1。

  2. 可直接使用大币

    dp[3]：1 via 3；dp[4]：1 via 4

    金额 3、4 各用一枚。

  3. 金额 5

    dp[4]：1；last coin：1；dp[5]：2

    从金额 4 加币 1，或金额 1 加币 4，都是两枚。

  4. 金额 6

    dp[3]：1；last coin：3；dp[6]：2

    从金额 3 加币 3 得两枚，优于 4+1+1。

跟着例子，走完一遍

例题 01C++20 · 本机可运行

最少硬币击破贪心

币值 [1,3,4]，金额 6；同时测试 [2] 无法凑 3 和金额零。

  1. dp[0]=0。
  2. 每个金额枚举最后一枚币。
  3. dp[6] 由 dp[3]+1 得到 2。
18-a.cpp
下载
#include <algorithm>
#include <iostream>
#include <span>
#include <stdexcept>
#include <vector>
int min_coins(std::span<const int> coins, int amount) {
    if (amount < 0 || amount > 10000) throw std::invalid_argument("amount range");
    for (const int c : coins) if (c <= 0) throw std::invalid_argument("positive coins required");
    const int impossible = amount + 1;
    std::vector<int> dp(static_cast<std::size_t>(amount) + 1, impossible);
    dp[0] = 0;
    for (int s = 1; s <= amount; ++s)
        for (const int c : coins)
            if (c <= s) dp[static_cast<std::size_t>(s)] = std::min(dp[static_cast<std::size_t>(s)], dp[static_cast<std::size_t>(s-c)] + 1);
    return dp[static_cast<std::size_t>(amount)] == impossible ? -1 : dp[static_cast<std::size_t>(amount)];
}
int main() {
    const std::vector<int> coins{1,3,4}, even{2};
    if (min_coins(coins, 6) != 2 || min_coins(even, 3) != -1 || min_coins(coins, 0) != 0) return 1;
    std::cout << "coins=" << min_coins(coins, 6) << " impossible=" << min_coins(even, 3)
              << " zero=" << min_coins(coins, 0) << '\n';
}

如何编译和运行下载的 .cpp 文件 →

结果与解释

coins=2 impossible=-1 zero=0

此题允许重复选择；只使用正币值，示例限制小金额避免无限内存要求。

在本机运行这个例子

下载后，在文件所在目录执行。需要支持 C++20 的编译器；POSIX 示例还需要章节说明中的系统条件。

clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 18-a.cpp -o example && ./example

预期标准输出：

coins=2 impossible=-1 zero=0
例题 02C++20 · 本机可运行

零一背包逆序避免重复用物品

重量 [2,3]，价值 [3,4]，容量 4，每件最多一次。

  1. 处理第一件逆序更新容量 4、3、2，最多价值 3。
  2. 处理第二件逆序更新容量 4、3，得到价值 4。
  3. 不能用两次重量 2 的物品。
18-b.cpp
下载
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
struct Item { int weight; int value; };
int main() {
    constexpr int capacity = 4;
    const std::array<Item,2> items{{{2,3},{3,4}}};
    std::vector<int> dp(static_cast<std::size_t>(capacity)+1, 0);
    for (const auto item : items)
        for (int c = capacity; c >= item.weight; --c)
            dp[static_cast<std::size_t>(c)] = std::max(dp[static_cast<std::size_t>(c)],
                dp[static_cast<std::size_t>(c-item.weight)] + item.value);
    if (dp[4] != 4 || dp[1] != 0 || dp[2] != 3) return 1;
    std::cout << "best=" << dp[4] << '\n';
}
结果与解释

best=4

逆序使本轮读取的较小容量仍属于上一物品阶段。

在本机运行这个例子

下载后，在文件所在目录执行。需要支持 C++20 的编译器；POSIX 示例还需要章节说明中的系统条件。

clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 18-b.cpp -o example && ./example

预期标准输出：

best=4
常见错误

压缩数组后忘记阶段

零一背包按容量从小到大更新，本轮已用当前物品的状态又被读取，暗中改成可重复使用。

修正思路：保持二维阶段推理；压缩后逆序容量，使用单件重量 2、容量 4 的反例检查。

轮到你动手

先写预测或代码，再按需打开提示。完整答案用于对照自己的推理。

练习 1

只有一件重量 2、价值 3 的物品，容量 4。正向与逆向更新各得到什么？

给我一点提示
  1. 观察 dp[2] 是否本轮刚更新。
  2. 零一语义最多选一次。
查看答案与推理

正向更新先使 dp[2]=3，再用它更新 dp[4]=6，错误地重复选同一件；逆向先算 dp[4]=3，再更新 dp[2]=3，正确答案 3。

练习 2

在 min_coins 中记录最后一枚硬币，如何恢复金额 6 的一个最优方案？

给我一点提示
  1. 每次严格改进 dp[s] 时记录 choice[s]。
  2. 从目标往零倒推。
查看答案与推理

choice[6]=3，先记录币 3，将金额降到 3；choice[3]=3，再降到 0，得到 [3,3]。无解时先返回失败，不能在未设置 choice 的状态循环。

把理解说出来

先用中文讲清因果，再用英文回答。问题依据技能主题编写，并非公司内部题库。

解释

写 DP 的第一步是什么？

参考回答 / English answer

完整定义状态含义，包括处理范围、容量是恰好还是至多、元素能否重复；然后推导转移。

Define exactly what each state means before writing the recurrence. Include the processed items, the capacity interpretation, and whether reuse is allowed.
预测

币值 1、3、4 凑 6，贪心和最优分别多少枚？

参考回答 / English answer

贪心 4+1+1 是 3 枚；最优 3+3 是 2 枚，说明该币系不保证贪心正确。

Greedy takes four plus one plus one, using three coins. The optimal solution uses two threes, so this coin system does not support that greedy rule.
找错

零一背包容量正序更新为什么错？

参考回答 / English answer

读到本轮已使用当前物品的状态，重复使用同一件，改变问题语义。

Ascending updates can read a state already improved by the current item. That allows the same item to be used again and changes the problem.
追问

dp[0] 为什么是零，而不是不可达？

参考回答 / English answer

金额零有合法空选择，成本为零；它是所有可达转移的起点。

The empty selection makes amount zero reachable with zero cost. That base state seeds every valid construction.
复杂度

O(amount×coin_count) 为什么可能仍太大？

参考回答 / English answer

依赖金额数值而非其编码长度；大金额会产生巨大状态数组，需根据约束重新设计。

The bound depends on the numeric amount, not just the length of its representation. A very large amount can make the state space impractical.
设计

从最优值恢复方案需要什么？

参考回答 / English answer

保留决策或足够状态供回溯，说明多个最优方案时的选择规则；空间压缩可能丢掉重建信息。

Store decisions or enough earlier states to reconstruct the choices. Space compression can discard information needed for reconstruction, so plan that requirement first.

继续查证

公开资料用于查证；本章图解和例题是独立教学内容。CPU 逻辑模型不能证明设备性能。

接着看已有的图解

这些资料按主题补充本章内容。