14.4 背包动态规划：选择次数、目标语义与循环顺序

背包最危险的学法，是背下“0-1 倒序、完全正序”就继续刷题。这样也许能过熟悉的模板题，却很难回答：为什么组合计数要先枚举物品？为什么目标和里的 0 会让方案数翻倍？为什么多重背包的二进制拆分不能无脑用于计数？

我们从一个不会混淆时间层的二维定义开始：

前 i 种物品，在容量/目标 c 下能得到什么？

之后的一维压缩、循环方向和各种题型都从这句话推出来。

1. 背包模型的四个开关

遇到“从若干对象中选一些，使总量满足目标”的题，先确定四件事：

开关	常见选项	它决定什么
每种对象可选次数	0/1、无限、有限、同组至多一个	转移来源和容量方向
容量语义	不超过、恰好、至少	初值、不可达值、答案位置
状态值	可行性、最大/最小值、方案数	聚合运算和单位元
顺序是否区分	组合、排列	物品循环与容量循环的先后

定义 · 0-1 背包状态

设物品 1..n 的重量、价值分别为 w[i]、v[i]。F[i][c] 表示只考虑前 i 件物品、总重量不超过 c 时的最大价值。每件物品只能选 0 次或 1 次。

完整案例 1 · 0-1 背包原型：从二维选/不选到一维倒序

1. 暴力与状态

每件物品都有“选/不选”两个分支，暴力枚举有 $2^{n}$ 个子集。不同选择历史只要处理到的物品前缀和剩余容量相同，未来问题就相同。

处理第 i 件物品时：

不选：F[i-1][c]；
若 w[i]<=c，选择：F[i-1][c-w[i]]+v[i]。

F [i] [c] = max (F [i - 1] [c], F [i - 1] [c - w_{i}] + v_{i})

2. 状态设计卡

问题	答案
阶段	已考虑前 `i` 件物品
状态	容量不超过 `c` 的最大价值
决策	第 `i` 件选或不选
边界	`F[0][c]=0`；容量上限语义允许不装满
顺序	`i` 递增；二维时容量方向任意
答案	`F[n][capacity]`

3. 手算

物品 (重量,价值) 为 (2,3),(3,4)，容量 4：

已处理物品	`2`	`3`	`4`
0 件	0	0	0
`(2,3)`	3	3	3
再加 `(3,4)`	3	4	4

容量 4 不能把第一件用两次，所以答案是 4。

4. 一维倒序为何必要

压缩后 f[c] 在第 i 轮开始时代表 F[i-1][c]。更新 f[c] 时必须读取旧层的 f[c-w]。容量从大到小，较小下标尚未被本轮覆盖；若正序，f[c-w] 可能已经选择过当前物品。

cpp

#include <algorithm>
#include <iostream>
#include <vector>

long long zeroOneKnapsack(const std::vector<int>& weight,
                          const std::vector<int>& value,
                          int capacity) {
    std::vector<long long> f(capacity + 1, 0);
    for (std::size_t i = 0; i < weight.size(); ++i) {
        for (int c = capacity; c >= weight[i]; --c) {
            f[c] = std::max(f[c], f[c - weight[i]] + value[i]);
        }
    }
    return f[capacity];
}

int main() {
    std::cout << zeroOneKnapsack({2, 3}, {3, 4}, 4) << '\n';
}

zero-one-knapsack.cpp

定理 · 0-1 背包转移

任意只使用前 i 件物品的合法集合，按是否包含第 i 件分成互斥两类。不包含时价值至多 F[i-1][c]；包含时删去该物品，剩余集合重量不超过 c-w[i]，价值至多 F[i-1][c-w[i]]。两类最优值取最大即为 F[i][c]。

复杂度 · 0-1 背包

n(capacity+1) 个二维状态，每个状态常数转移，时间 $O (n \cdot c a p a c i t y)$ ；一维压缩空间 $O (c a p a c i t y)$ 。这是伪多项式复杂度：它依赖容量的数值，而非容量二进制表示长度。

反例 · 0-1 背包正序会复用同一物品

只有一件 (w=2,v=3)，容量 4。正序更新时先令 f[2]=3，到 c=4 又读取本轮刚更新的 f[2]，得到 f[4]=6，等价于把唯一物品选了两次。倒序时计算 f[4] 读取的是旧 f[2]=0，答案保持 3。

迁移： 若状态要求“恰好装满”，不能把所有容量初始化为 0；应设 f[0]=0，其余为 -INF，否则“不选任何物品”会被误认为能恰好达到任意容量。

完整案例 2 · 分割等和子集：最大值改成可行性

1. 代数转换

把正整数数组分成和相等的两个子集。总和为 sum；若它为奇数，立即无解。否则只需判断是否存在一个子集和恰好为 target=sum/2。

状态值不再是最大价值，而是布尔可达性：

f[c]：使用已处理数字，能否恰好组成和 c。

处理数字 x：f[c] = f[c] || f[c-x]，仍是每个数字最多一次，所以容量倒序。

2. 状态设计卡

问题	答案
选择次数	每个数组元素 0 或 1 次
目标语义	恰好达到 `target`
状态值	布尔可行性
边界	`f[0]=true`，其它为 `false`
顺序	先元素，容量倒序
答案	`f[target]`

对 [1,5,11,5]，目标为 11；处理到第三个数时 f[11] 可由单个 11 达到，另一子集和也为 11。

cpp

#include <iostream>
#include <numeric>
#include <vector>

bool canPartition(const std::vector<int>& numbers) {
    const int total = std::accumulate(numbers.begin(), numbers.end(), 0);
    if (total % 2 != 0) return false;
    const int target = total / 2;
    std::vector<char> f(target + 1, false);
    f[0] = true;

    for (int x : numbers) {
        for (int c = target; c >= x; --c) {
            f[c] = static_cast<char>(f[c] || f[c - x]);
        }
    }
    return f[target];
}

int main() {
    std::cout << std::boolalpha << canPartition({1, 5, 11, 5}) << '\n';
}

partition-equal-subset-sum.cpp

证明

对已处理元素数归纳。达到和 c 的子集要么不含当前元素，保持旧 f[c]；要么包含它，删去后必须由旧元素达到 c-x。两类的逻辑或恰好描述可行性。倒序保证第二类不重复使用当前元素。

复杂度 · 等和划分

目标为 sum/2，时间 $O (n \cdot s u m)$ 、空间 $O (s u m)$ 。若数值总和极大，这种伪多项式 DP 可能不适用，应结合 n、值域或 meet-in-the-middle 等方法重新判断。

易错点 · `vector<bool>` 的代理引用

vector<bool> 采用位压缩代理语义，简单使用通常可行，但调试引用和泛型代码时容易困惑。本例用 vector<char> 明确表示 0/1 状态。

迁移： “最后一块石头的重量 II”不是判断恰好一半，而是在不超过一半的容量中最大化可达子集和，最后返回 total-2*best。

完整案例 3 · 目标和：符号选择如何变成子集计数

1. 从正负号到两个集合

给每个非负整数添加 + 或 -，使表达式结果为 target，求方案数。设加号集合之和为 P，减号集合之和为 N：

P - N = t a r g e t, P + N = s u m

相加得：

2 P = s u m + t a r g e t

因此转成：从数组中选择一个子集，使其和恰好为 bag=(sum+target)/2，求子集数量。

若 abs(target)>sum 或 sum+target 为奇数，则无解。

2. 状态设计卡

问题	答案
状态	`f[c]`：用已处理元素组成和 `c` 的子集数量
边界	`f[0]=1`，空子集是一种方案
转移	`f[c]+=f[c-x]`
顺序	先元素，容量倒序
答案	`f[bag]`

对 [1,1,1,1,1]、目标 3，bag=(5+3)/2=4。选择任意四个 1 作为正号集合，共 5 种。

cpp

#include <cstdlib>
#include <iostream>
#include <numeric>
#include <vector>

long long countTargetExpressions(const std::vector<int>& numbers, int target) {
    const int total = std::accumulate(numbers.begin(), numbers.end(), 0);
    if (std::abs(target) > total || (total + target) % 2 != 0) return 0;
    const int bag = (total + target) / 2;
    if (bag < 0) return 0;

    std::vector<long long> f(bag + 1, 0);
    f[0] = 1;
    for (int x : numbers) {
        for (int c = bag; c >= x; --c) {
            f[c] += f[c - x];
        }
    }
    return f[bag];
}

int main() {
    std::cout << countTargetExpressions({1, 1, 1, 1, 1}, 3) << '\n';
}

target-sum.cpp

定理 · 代数转换保持一一对应

每种正负号赋值唯一确定正号元素子集 P，且满足目标当且仅当其和为 (sum+target)/2；反之，每个满足该和的下标子集唯一决定哪些位置取正号。即使数值相同，不同下标仍对应不同表达式，因此子集计数正确。

复杂度 · 目标和

设转换后容量为 bag，时间 $O (n \cdot b a g)$ 、空间 $O (b a g)$ 。方案数可能很大，应按题目要求选择 long long 或取模。

易错点 · 零元素会让方案数翻倍

处理 x=0 时，倒序循环在 c 处执行 f[c]+=f[c]，恰好表示这个零可取正号或负号，数值和不变但表达式不同。不要为了避免“自己加自己”而跳过零。

迁移： 若原数组允许负数，上述总和与子集转换需重新推导；不要在代数前提失效时继续套非负背包。

完整案例 4 · 零钱兑换：完全背包求最少数量

1. 为什么容量要正序

每种硬币可使用无限次，求恰好组成金额 amount 的最少硬币数。令：

f[c] 表示用已处理硬币种类恰好组成金额 c 的最少数量。

处理硬币 coin 时，若选择一枚，仍可继续使用同种硬币。因此 f[c-coin] 应当允许包含当前硬币，也就是本轮已经更新的新层状态。容量从小到大正好满足这一点。

f [c] = min (f [c], f [c - c o i n] + 1)

2. 状态设计卡

问题	答案
选择次数	每种硬币无限次
状态	恰好组成金额 `c` 的最少硬币数
边界	`f[0]=0`，其余 `INF`
顺序	先硬币，容量正序
答案	`f[amount]`，不可达则 `-1`

对硬币 [1,3,4]、金额 6：处理硬币 3 时，f[3]=1，随后 f[6] 可读取本轮 f[3] 得到 2，表示硬币 3 使用两次。

cpp

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

int minimumCoins(const std::vector<int>& coins, int amount) {
    const int INF = std::numeric_limits<int>::max() / 4;
    std::vector<int> f(amount + 1, INF);
    f[0] = 0;

    for (int coin : coins) {
        for (int c = coin; c <= amount; ++c) {
            if (f[c - coin] != INF) {
                f[c] = std::min(f[c], f[c - coin] + 1);
            }
        }
    }
    return f[amount] == INF ? -1 : f[amount];
}

int main() {
    std::cout << minimumCoins({1, 3, 4}, 6) << '\n';
}

coin-change-minimum.cpp

证明

按硬币种类归纳。使用前 i 种硬币组成金额 c 的最优方案，要么不用第 i 种，保留旧 f[c]；要么至少使用一枚，删去一枚后仍是使用前 i 种硬币组成 c-coin 的最优子问题。正序更新使该状态已包含当前硬币的任意次使用，重复应用转移覆盖 1、2、3……枚。

复杂度 · 零钱兑换最少数

m 种硬币与 amount+1 个金额状态，时间 $O (m \cdot a m o u n t)$ 、空间 $O (a m o u n t)$ 。

易错点 · 先金额还是先硬币对最小值可能同样正确，但语义不同

本例只求最少件数，按金额枚举再尝试所有硬币也能得到同样最短路径式递推。但进入方案计数后，循环顺序会决定组合还是排列，不能据此认为循环可随意交换。

迁移： 完全平方数可把每个平方数视作可无限使用的物品，求组成 n 的最少件数。

完整案例 5 · 零钱兑换 II：组合计数为什么先枚举硬币

现在仍有无限硬币，但问组成金额的组合数，不同使用顺序不算新方案。例如硬币 {1,2} 凑 3，组合只有 {1,1,1} 与 {1,2} 两种。

定义 f[c] 为使用已处理硬币种类组成金额 c 的组合数。外层依次引入硬币，相当于规定每个组合按硬币种类分阶段生成；同一组合不会因选取顺序不同重复出现。

状态设计卡

问题	答案
状态	使用已处理硬币种类组成金额 `c` 的组合数
边界	`f[0]=1`
转移	`f[c]+=f[c-coin]`
顺序	外层硬币，内层容量正序
答案	`f[amount]`

手算硬币 {1,2}：

阶段	`f[0]`	`f[1]`	`f[2]`	`f[3]`
空集合	1	0	0	0
加入硬币 1	1	1	1	1
加入硬币 2	1	1	2	2

cpp

#include <iostream>
#include <vector>

long long countCombinations(const std::vector<int>& coins, int amount) {
    std::vector<long long> f(amount + 1, 0);
    f[0] = 1;
    for (int coin : coins) {
        for (int c = coin; c <= amount; ++c) {
            f[c] += f[c - coin];
        }
    }
    return f[amount];
}

int main() {
    std::cout << countCombinations({1, 2}, 3) << '\n';
}

coin-change-combinations.cpp

证明

处理完第 i 种硬币后，每个被计数的组合只含前 i 种硬币。新增组合至少含一枚第 i 种硬币，删去一枚后对应一个金额 c-coin 的本阶段组合；加回硬币得到唯一逆映射。因为硬币种类按固定阶段引入，组合 {1,2} 不会再以 {2,1} 被第二次生成。

复杂度 · 组合计数

时间 $O (m \cdot a m o u n t)$ 、空间 $O (a m o u n t)$ 。若硬币面额可能重复，应先明确输入中的两个相同面额是否视作不同种类；通常需去重或题目保证唯一。

易错点 · `f[0]=1` 是空组合

没有硬币时组成金额 0 有一种方式：什么也不选。若初始化为 0，任何非零金额都无法从转移产生方案。

迁移： 如果每种硬币有使用上限，状态还需限制数量；简单正序会越过上限，应使用多重背包的分组、枚举数量或专门优化。

完整案例 6 · 组合总和 IV：排列计数为什么先枚举容量

给定互不相同的正数，可以重复使用，求和为 target 的有序序列数。对 {1,2}、目标 3，序列为：

text

1+1+1
1+2
2+1

这里最后一个选择的位置有意义。定义：

f[c] 表示和恰好为 c 的有序序列数。

按总和从小到大计算，并枚举最后一个数 x：

f [c] = \sum_{x \leq c} f [c - x]

状态设计卡

问题	答案
状态	和为 `c` 的有序序列数
最后一步	序列最后放入哪个数 `x`
边界	`f[0]=1`，空前缀
顺序	外层容量递增，内层枚举选择
答案	`f[target]`

cpp

#include <iostream>
#include <vector>

long long countOrderedSequences(const std::vector<int>& numbers, int target) {
    std::vector<long long> f(target + 1, 0);
    f[0] = 1;
    for (int sum = 1; sum <= target; ++sum) {
        for (int x : numbers) {
            if (x <= sum) f[sum] += f[sum - x];
        }
    }
    return f[target];
}

int main() {
    std::cout << countOrderedSequences({1, 2}, 3) << '\n';
}

combination-sum-ordered.cpp

定理 · 按最后一个数划分排列

每个非空有序序列都有唯一最后一个数 x。删除它后得到和为 c-x 的有序序列；反之给任意该前缀追加 x，得到唯一和为 c 的序列。按最后一个数划分的集合互斥且覆盖全部方案，因此求和正确。

复杂度 · 排列计数

时间 $O (m \cdot t a r g e t)$ 、空间 $O (t a r g e t)$ 。计数增长可能非常快，实际题目常需无符号范围、任意精度或取模。

反例 · 组合与排列只差循环顺序，却差一个答案

硬币 {1,2}、目标 3：外层硬币只得到 2 个无序组合；外层容量按最后一个数划分得到 3 个有序序列。循环顺序不是性能细节，它编码了“方案相同”的定义。

迁移： 若数字允许 0 或负数，有序序列可能无限多或形成环，按总和递增的依赖不再成立。正数条件是这段 DP 的结构前提。

2. 迁移案例：模型不变，目标或资源维度改变

迁移案例 A · 最后一块石头的重量 II

把石头分到两组，最终差值为 total-2*group。只需在容量 total/2 内做 0-1 背包，让 group 尽量大：

状态：不超过容量 c 的最大可达重量；
转移：f[c]=max(f[c],f[c-stone]+stone)，容量倒序；
答案：total-2*f[total/2]；
复杂度： $O (n \cdot t o t a l)$ 时间、 $O (t o t a l)$ 空间。

它与等和划分共享状态空间，但一个问“能否恰好一半”，一个问“离一半最近”。

迁移案例 B · 完全平方数

把 1^2,2^2,... 视作无限物品，组成 n 的最少件数：

f[0]=0，其余 INF；
外层枚举平方数，容量正序；
f[c]=min(f[c],f[c-square]+1)；
时间约 $O (n \sqrt{n})$ ，空间 $O (n)$ 。

也可按金额外层枚举最后一个平方数，最小值结果相同；但要能用“最后一步”解释，而不是因为两个循环碰巧都过样例。

迁移案例 C · 一和零：二维容量 0-1 背包

每个二进制字符串消耗若干个 0 和 1，最多选多少字符串。状态变成：

f[z][o]：0 容量不超过 z、1 容量不超过 o 时最多选几个字符串。

每个字符串只能选一次，所以两个容量维度都倒序：

f [z] [o] = max (f [z] [o], f [z - z e r o] [o - o n e] + 1)

时间 $O (n Z O)$ 、空间 $O (Z O)$ 。增加维度的原因是未来同时受两种独立资源约束。

迁移案例 D · 分组背包

物品分组，每组至多选一件。二维状态按组推进：

F [g] [c] = max (F [g - 1] [c], max_{i t e m \in g r o u p_{g}, w \leq c} F [g - 1] [c - w] + v)

一维压缩时外层是组，容量倒序，最内层枚举当前组物品；所有候选必须读取组开始前的旧层，避免同组选择多件。若实现顺序不易保证，保留二维表更安全。

迁移案例 E · 多重背包与二进制拆分边界

每种物品最多 count 件，朴素转移枚举 k=0..count：

F [i] [c] = max_{0 \leq k \leq c o u n t, k w \leq c} F [i - 1] [c - k w] + k v

可把数量拆成 1,2,4,...,remaining 组，转成若干 0-1 物品，使 0..count 的每种选取数量都能由这些组表达，复杂度降到 $O (c a p a c i t y \sum \log c o u n t_{i})$ 。这里需要的是“所有数量都可表达”，并不保证每个数量只有一种拆分方式。

易错点 · 计数问题不能机械二进制拆分

在求最大价值时，只关心某个数量能否表达；不同拆分选法得到同一件数不会改变最优值。但在方案计数中，人造分组可能把同一种原方案重复计数或改变“物品是否可区分”的语义。优化前必须证明拆分与原方案之间是一一对应，而不是看到“多重背包”就套二进制。

3. 一张循环顺序判定表

模型	外层	容量方向	读取的 `f[c-w]` 语义
0-1 最值/可行/计数	物品	大 → 小	上一物品层，当前物品未使用
完全背包最值/可行	物品	小 → 大	当前物品层，允许继续使用
完全背包组合计数	物品	小 → 大	只用已引入种类的组合
完全选择排列计数	容量	内层选择	按最后一个选择划分序列
二维容量 0-1	物品	两维均倒序	所有资源坐标均来自旧层
分组背包	组	容量倒序，组内枚举	组开始前的旧层

直觉 · 不背方向，追问当前物品能否再次出现

更新 f[c] 时看 f[c-w]：如果你希望它已经包含当前物品，就正序；如果你要求它仍属于上一层、尚未使用当前物品，就倒序。计数题还要继续问：外层阶段是在固定物品集合，还是在固定序列长度/总和？

4. “恰好、至多、至少”如何改变初值

同一个转移，初值不同就代表不同问题：

目标	最大值常见初始化	最小值常见初始化	计数初始化
容量不超过 `c`	全 0，允许空选择	视题意而定	通常不直接对应
恰好达到 `c`	`f[0]=0`，其它 `-INF`	`f[0]=0`，其它 `INF`	`f[0]=1`，其它 0
至少达到目标	可扩大状态或把超出部分夹到目标	`f[0]=0` 后向上覆盖	需明确超出是否合并

不可达哨兵必须与聚合运算匹配：最大化用 -INF，最小化用 INF，计数用 0。转移前还要避免对哨兵做会溢出的加法。

5. 本节复盘与最小反例

写背包代码前，逐项回答：

一件对象可用几次？相同数值的对象按下标是否可区分？
容量是上限，还是必须恰好达到？
状态保存可行性、最值还是方案数？
顺序不同算不算新方案？
压缩时 f[c-w] 应来自旧层还是当前层？
空集合/空序列为什么是 0、1、INF 或 -INF？
数值范围是否让伪多项式复杂度失去可行性？

至少保留两个单元级反例：

一件 (2,3)、容量 4：0-1 正序错误地产生价值 6；
{1,2}、目标 3：组合数 2、排列数 3，验证循环层次。

对拍建议

当 n≤15 时枚举所有子集验证 0-1 背包、等和划分和目标和；当目标很小时，用递归枚举有限长度序列验证组合/排列计数。循环方向错误往往能被容量 3～6 的极小输入抓住，不需要等到大样例。

6. 本阶段之后如何继续

完成 01～04 后，你已经拥有后续 DP 的共同语言：

序列与划分 DP：状态从单前缀扩成双前缀、结尾或最后分界点；
状态机 DP：用有限末态保存会影响未来的历史；
区间 DP：阶段从前缀变成区间长度，决策常是最后分界点；
状压 DP：当“已经选择哪些对象”确实影响未来时，用位集合保存必要历史；
树形/图上 DP：状态依赖不再由数组坐标给出，而由结构边和拓扑关系给出。

不要把背包当成动态规划的全部。它真正教会我们的，是如何从选择次数、资源约束和方案等价关系推出状态与循环。

参考与训练入口

OI Wiki：背包 DP：校验 0-1、完全、多重、分组以及常见优化的知识边界。
灵茶山艾府：动态规划题单：背包分类按 0-1、完全、多重、分组及变体提供训练梯度。
本文题意均为压缩改写，证明与 C++17 代码独立编写；具体数据范围、取模和输入合同应以原题页面为准。

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

1. 背包模型的四个开关 ​

完整案例 1 · 0-1 背包原型：从二维选/不选到一维倒序 ​

1. 暴力与状态 ​

2. 状态设计卡 ​

3. 手算 ​

4. 一维倒序为何必要 ​

完整案例 2 · 分割等和子集：最大值改成可行性 ​

1. 代数转换 ​

2. 状态设计卡 ​

完整案例 3 · 目标和：符号选择如何变成子集计数 ​

1. 从正负号到两个集合 ​

2. 状态设计卡 ​

完整案例 4 · 零钱兑换：完全背包求最少数量 ​

1. 为什么容量要正序 ​

2. 状态设计卡 ​

完整案例 5 · 零钱兑换 II：组合计数为什么先枚举硬币 ​

状态设计卡 ​

完整案例 6 · 组合总和 IV：排列计数为什么先枚举容量 ​

状态设计卡 ​

2. 迁移案例：模型不变，目标或资源维度改变 ​

迁移案例 A · 最后一块石头的重量 II ​

迁移案例 B · 完全平方数 ​

迁移案例 C · 一和零：二维容量 0-1 背包 ​

迁移案例 D · 分组背包 ​

迁移案例 E · 多重背包与二进制拆分边界 ​

3. 一张循环顺序判定表 ​

4. “恰好、至多、至少”如何改变初值 ​

5. 本节复盘与最小反例 ​

6. 本阶段之后如何继续 ​

参考与训练入口 ​

1. 背包模型的四个开关

完整案例 1 · 0-1 背包原型：从二维选/不选到一维倒序

1. 暴力与状态

2. 状态设计卡

3. 手算

4. 一维倒序为何必要

完整案例 2 · 分割等和子集：最大值改成可行性

1. 代数转换

2. 状态设计卡

完整案例 3 · 目标和：符号选择如何变成子集计数

1. 从正负号到两个集合

2. 状态设计卡

完整案例 4 · 零钱兑换：完全背包求最少数量

1. 为什么容量要正序

2. 状态设计卡

完整案例 5 · 零钱兑换 II：组合计数为什么先枚举硬币

状态设计卡

完整案例 6 · 组合总和 IV：排列计数为什么先枚举容量

状态设计卡

2. 迁移案例：模型不变，目标或资源维度改变

迁移案例 A · 最后一块石头的重量 II

迁移案例 B · 完全平方数

迁移案例 C · 一和零：二维容量 0-1 背包

迁移案例 D · 分组背包

迁移案例 E · 多重背包与二进制拆分边界

3. 一张循环顺序判定表

4. “恰好、至多、至少”如何改变初值

5. 本节复盘与最小反例

6. 本阶段之后如何继续

参考与训练入口