Hello 算法：完全背包、零钱兑换与零钱兑换 II —— 动态规划中"正序遍历"的空间优化

本文基于《Hello 算法》动态规划章节的完全背包问题文档，系统讲解完全背包问题的状态转移推导、代码实现与空间优化，并深入剖析其两个经典变种——零钱兑换（求最少硬币数）与零钱兑换 II（求硬币组合数）。读完后，你将能够独立推导"物品可重复选取"这一约束下的 DP 方程，并理解为什么完全背包的空间优化必须使用正序遍历（与 0-1 背包的倒序遍历正好相反），同时掌握用 amt + 1 代替 +∞ 避免整数溢出的工程技巧。

一、完全背包问题

1.1 问题定义

给定 n 个物品，第 i 个物品的重量为 wgt[i-1]、价值为 val[i-1]，和一个容量为 cap 的背包。每个物品可以重复选取，问在限定背包容量下能放入物品的最大价值。

文档给出的示例数据（也与源码 Driver Code 一致）为：wgt = [1, 2, 3]，val = [5, 11, 15]，cap = 4。

可以验证：背包容量 4 时，最优解是放入 4 份重量 1 的物品（价值 20），或者 2 份重量 2 的物品（价值 22），因此最终答案应为 22。

1.2 与 0-1 背包的本质区别

完全背包问题和 0-1 背包问题非常相似，区别仅在于不限制物品的选择次数。这正是两题状态转移的源头差异：

• 在 0-1 背包中，每种物品只有一个，因此将物品 i 放入背包后，只能从前 i-1 个物品中选择；
• 在完全背包中，每种物品的数量是无限的，因此将物品 i 放入背包后，仍可以从前 i 个物品中选择（包括物品 i 本身）。

状态 [i, c]（考虑前 i 个物品、容量为 c 时的最大价值）的变化分为两种情况：

• 不放入物品 i：与 0-1 背包相同，转移至 [i-1, c]；
• 放入物品 i：与 0-1 背包不同，转移至 [i, c - wgt[i-1]]（注意行号仍是 i 而不是 i-1）。

从而状态转移方程变为：

$$dp[i, c] = \max(dp[i-1, c],\ dp[i, c - wgt[i-1]] + val[i-1])$$

1.3 代码实现：只有一处从 i-1 变为 i

在 Python 参考实现 unbounded_knapsack.py 中，二维 DP 版本 unbounded_knapsack_dp 的核心循环如下：

def unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
    """完全背包：动态规划"""
    n = len(wgt)
    # 初始化 dp 表
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    # 状态转移
    for i in range(1, n + 1):
        for c in range(1, cap + 1):
            if wgt[i - 1] > c:
                # 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c]
            else:
                # 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
    return dp[n][cap]

把这段代码与 0-1 背包的实现 knapsack.py 中的 knapsack_dp 逐行对比，会发现两者唯一的区别就在转移式中"选物品"那一支的下标：

# 0-1 背包（knapsack_dp）：dp[i - 1][c - wgt[i - 1]] + val[i - 1]
# 完全背包（unbounded_knapsack_dp）：dp[i][c - wgt[i - 1]] + val[i - 1]

dp[i-1][...] 意味着"选完物品 i 后不能再选物品 i"，dp[i][...] 意味着"选完物品 i 后还可以继续选物品 i"——一个下标之差，精确编码了"物品是否可重复选取"这一语义。C++ 实现 unbounded_knapsack.cpp 中的 unboundedKnapsackDP 逻辑完全一致。

1.4 空间优化：正序遍历是关键

二维表 dp[i][c] 只依赖于"上一行"的 dp[i-1][c] 与"同一行左侧"的 dp[i][c - wgt[i-1]]。删除第一维、用一维数组 dp[c] 滚动更新时，遍历方向决定了 dp[c - wgt[i-1]] 取到的是"上一轮的值"还是"本轮刚更新的值"：

• 完全背包：当前状态需要引用本轮已更新的同状态（体现"可重复选取"），因此对每一行必须正序遍历（c 从 1 到 cap）；
• 0-1 背包：当前状态必须引用上一轮未更新的值（体现"只选一次"），因此必须倒序遍历（c 从 cap 到 1）。

这个遍历顺序与 0-1 背包正好相反。文档配了 6 张连续动图展示一维化后的转移过程（状态从"左边和上边"即"左侧和上方"扩散而来），其中一张步骤图如下：

（完整 6 步序列见 unbounded_knapsack_dp_comp_step1.png 至 unbounded_knapsack_dp_comp_step6.png。）

以示例数据手动推演一遍正序遍历，可以更直观地看到"同轮复用"如何发生：处理物品 3（重 3、值 15）这一轮，c 从 1 增至 4；当 c = 4 时，dp[4] = max(dp[4], dp[4-3] + 15)，而 dp[1] 在本轮 c = 1 时已经因选取物品 3 更新为 15，于是 dp[4] = max(22, 15 + 15) = 22……最终 dp[4] = 22，即 2 份物品 2（价值 2×11）。若换成倒序遍历，dp[1] 在 c=4 时还未更新，"选两份物品 2"的路径就不存在——这正是遍历顺序决定语义的根源。

空间优化后的 Python 实现，仅需将数组 dp 的第一维删除（对应 unbounded_knapsack.py 的 unbounded_knapsack_dp_comp）：

def unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
    """完全背包：空间优化后的动态规划"""
    n = len(wgt)
    # 初始化 dp 表
    dp = [0] * (cap + 1)
    # 状态转移
    for i in range(1, n + 1):
        # 正序遍历
        for c in range(1, cap + 1):
            if wgt[i - 1] > c:
                # 若超过背包容量，则不选物品 i
                dp[c] = dp[c]
            else:
                # 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
    return dp[cap]

源码文件末尾的 Driver Code 同时运行两个版本，输入 wgt = [1, 2, 3]、val = [5, 11, 15]、cap = 4，两版本输出一致。C++ 版本 unbounded_knapsack.cpp 的 unboundedKnapsackDPComp 同样采用 for (int c = 1; c <= cap; c++) 的正序循环。

小结：完全背包空间优化的两条规则——① 删除物品维度，dp[c] 初值为 0（价值类问题，容量为 0 时价值自然为 0）；② 容量维度正序遍历。与 0-1 背包（初值 0、倒序遍历）形成对照，这是面试与竞赛中最高频的易错点之一。

二、零钱兑换问题（完全背包的特例）

背包问题是一大类动态规划问题的代表，其拥有很多变种，例如零钱兑换问题。

2.1 问题定义

给定 n 种硬币，第 i 种硬币的面值为 coins[i - 1]，目标金额为 amt，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额，则返回 -1。示例数据为 coins = [1, 2, 5]，amt = 4（源码 Driver Code 使用完全相同的输入，预期最少硬币数为 2，即 2 + 2）。

2.2 与完全背包的联系与不同

零钱兑换可以看作完全背包问题的一种特殊情况，两者可以相互转换，同时存在三点关键差异：

维度	完全背包	零钱兑换
概念对应	物品 / 重量 / 背包容量 / 价值	硬币 / 面值 / 目标金额 / 硬币数量
优化方向	最大化价值（max）	最小化硬币数（min）
容量语义	"不超过"容量 cap 的最大价值	"恰好凑到" amt 的最少硬币数

"恰好 vs 不超过"的差异直接体现在边界初始化上：完全背包首行首列全 0（容量为 0 时价值 0，且允许"没装满"）；零钱兑换首列全 0、首行（除首列外）为无效解。

2.3 三步推导 DP

第一步：定义状态，得到 dp 表。 状态 [i, a] 对应的子问题为：前 i 种硬币能够凑出金额 a 的最少硬币数量，记为 dp[i, a]。二维 dp 表的尺寸为 (n+1) × (amt+1)。

第二步：最优子结构，推导状态转移方程。 与完全背包的方程相比只有两点差异：

• 本题要求最小值，因此将运算符 max() 更改为 min()；
• 优化主体是硬币数量而非商品价值，因此在选中硬币时执行 +1 即可。

$$dp[i, a] = \min(dp[i-1, a],\ dp[i, a - coins[i-1]] + 1)$$

第三步：确定边界条件和状态转移顺序。

• 当目标金额为 0 时，凑出它的最少硬币数量为 0，即首列所有 dp[i, 0] 都等于 0（二维表默认初值 0 恰好满足，无需显式初始化）；
• 当无硬币时，无法凑出任意 > 0 的目标金额，是无效解。为使 min() 函数能够识别并过滤无效解，用 +∞ 表示它们，即令首行所有 dp[0, a]（a > 0）都等于 +∞。

2.4 代码实现：用 amt + 1 代替 +∞ 防溢出

大多数编程语言并未提供 +∞ 变量，只能使用整型 int 的最大值来代替。而这又会导致大数越界：状态转移方程中的 +1 操作可能发生溢出。

为此，源码采用数字 amt + 1 来表示无效解——因为凑出 amt 的硬币数量最多为 amt（全用面值为 1 的硬币），任何超过 amt 的值都必然无效，且 amt + 1 加 1 后最多为 amt + 2，远不会触及整数上限。最后返回前判断 dp[n, amt] 是否等于 amt + 1，若是则返回 -1。

Python 参考实现 coin_change.py 完整呈现了这一技巧：

def coin_change_dp(coins: list[int], amt: int) -> int:
    """零钱兑换：动态规划"""
    n = len(coins)
    MAX = amt + 1
    # 初始化 dp 表
    dp = [[0] * (amt + 1) for _ in range(n + 1)]
    # 状态转移：首行首列
    for a in range(1, amt + 1):
        dp[0][a] = MAX
    # 状态转移：其余行和列
    for i in range(1, n + 1):
        for a in range(1, amt + 1):
            if coins[i - 1] > a:
                # 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a]
            else:
                # 不选和选硬币 i 这两种方案的较小值
                dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
    return dp[n][amt] if dp[n][amt] != MAX else -1

注意二维表初始化时首列 dp[i][0] 保持 0（与 2.3 的边界条件一致），而首行 dp[0][a] 被显式置为 MAX = amt + 1。C++ 实现 coin_change.cpp 的 coinChangeDP 结构相同。

文档用 15 张连续动图展示了零钱兑换的完整填表过程，与完全背包非常相似（注意"恰好"语义使首行的无效解 amt+1 像"波浪"一样向右传播）：

（完整 15 步序列见 coin_change_dp_step1.png 至 coin_change_dp_step15.png。）

2.5 空间优化

零钱兑换的空间优化处理方式与完全背包一致：同样正序遍历。但初值有一个本质区别——因为要求"恰好凑到"，容量（金额）为 0 以外的位置初始都是无效解，所以一维表要整体初始化为 MAX = amt + 1，仅 dp[0] = 0：

def coin_change_dp_comp(coins: list[int], amt: int) -> int:
    """零钱兑换：空间优化后的动态规划"""
    n = len(coins)
    MAX = amt + 1
    # 初始化 dp 表
    dp = [MAX] * (amt + 1)
    dp[0] = 0
    # 状态转移
    for i in range(1, n + 1):
        # 正序遍历
        for a in range(1, amt + 1):
            if coins[i - 1] > a:
                # 若超过目标金额，则不选硬币 i
                dp[a] = dp[a]
            else:
                # 不选和选硬币 i 这两种方案的较小值
                dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
    return dp[amt] if dp[amt] != MAX else -1

对比 0-1 背包空间优化（dp = [0] * (cap + 1) + 倒序遍历）与完全背包空间优化（dp = [0] * (cap + 1) + 正序遍历），零钱兑换空间优化为（dp = [MAX] * (amt+1)、dp[0] = 0 + 正序遍历）——初值编码了"恰好/不超过"的语义，遍历方向编码了"可重复/不可重复"的语义，两者正交，组合出所有变种的优化规则。

三、零钱兑换问题 II：求组合数量

3.1 问题定义

给定 n 种硬币，第 i 种硬币的面值为 coins[i - 1]，目标金额为 amt，每种硬币可以重复选取，问凑出目标金额的硬币组合数量（注意：求的是"组合数"而非"最少数量"，且不计顺序）。示例数据 coins = [1, 2, 5]，amt = 5，预期答案为 4 种组合：[5]、[1,1,1,2]、[1,1,3… ]——实际为 [5]、[1,1,1,1,1]、[1,1,1,2]、[1,2,2]。

3.2 状态转移：从 min 到求和

相比于上一题，本题目标是求组合数量，因此子问题变为：前 i 种硬币能够凑出金额 a 的组合数量。而 dp 表仍然是尺寸为 (n+1) × (amt + 1) 的二维矩阵。

当前状态的组合数量等于"不选当前硬币"与"选当前硬币"这两种决策的组合数量之和（加法原理），状态转移方程为：

$$dp[i, a] = dp[i-1, a] + dp[i, a - coins[i-1]]$$

边界条件与零钱兑换 I 不同：

• 当目标金额为 0 时，无须选择任何硬币即可凑出目标金额（空方案算一种），因此应将首列所有 dp[i, 0] 都初始化为 1（而不是 0）；
• 当无硬币时，无法凑出任何 > 0 的目标金额，因此首行所有 dp[0, a] 都等于 0（二维表默认初值 0 恰好满足）。

3.3 代码实现

Python 参考实现 coin_change_ii.py：

def coin_change_ii_dp(coins: list[int], amt: int) -> int:
    """零钱兑换 II：动态规划"""
    n = len(coins)
    # 初始化 dp 表
    dp = [[0] * (amt + 1) for _ in range(n + 1)]
    # 初始化首列
    for i in range(n + 1):
        dp[i][0] = 1
    # 状态转移
    for i in range(1, n + 1):
        for a in range(1, amt + 1):
            if coins[i - 1] > a:
                # 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a]
            else:
                # 不选和选硬币 i 这两种方案之和
                dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
    return dp[n][amt]

3.4 空间优化：删除硬币维度

空间优化处理方式相同——同样删除硬币维度、同样正序遍历（"选当前硬币"支引用同轮已更新的 dp[a - coins[i-1]]，保证组合按硬币种类有序枚举、不产生重复排列）：

def coin_change_ii_dp_comp(coins: list[int], amt: int) -> int:
    """零钱兑换 II：空间优化后的动态规划"""
    n = len(coins)
    # 初始化 dp 表
    dp = [0] * (amt + 1)
    dp[0] = 1
    # 状态转移
    for i in range(1, n + 1):
        # 正序遍历
        for a in range(1, amt + 1):
            if coins[i - 1] > a:
                # 若超过目标金额，则不选硬币 i
                dp[a] = dp[a]
            else:
                # 不选和选硬币 i 这两种方案之和
                dp[a] = dp[a] + dp[a - coins[i - 1]]
    return dp[amt]

C++ 实现可见 coin_change_ii.cpp，各语言实现（Java、Go、Rust 等）均遵循同一套转移式与遍历方向。

四、横向对照：三个问题的 DP 要素速查

要素	0-1 背包	完全背包	零钱兑换 I	零钱兑换 II
物品约束	每种选 0/1 次	可重复选取	可重复选取	可重复选取
优化目标	最大价值	最大价值	最少硬币数	组合数量
转移式	max(dp[i-1][c], dp[i-1][c-w]+v)	max(dp[i-1][c], dp[i][c-w]+v)	min(dp[i-1][a], dp[i][a-coins]+1)	dp[i-1][a] + dp[i][a-coins]
容量语义	不超过	不超过	恰好	恰好
二维表初值	全 0	全 0	首列 0，首行 amt+1	首列 1，其余 0
一维表初值	[0]*(cap+1)	[0]*(cap+1)	[MAX]*(amt+1), dp[0]=0	[0]*(amt+1), dp[0]=1
遍历方向（一维）	倒序	正序	正序	正序
特殊返回值	无	无	无效解返回 -1	无
参考实现	knapsack.py	unbounded_knapsack.py	coin_change.py	coin_change_ii.py

三个要点可以一句话记忆：转移式中"选物品"那支的行号（i 还是 i-1）决定物品能否重复；一维化后的遍历方向必须与之保持一致（i-1 对应倒序、i 对应正序）；"恰好"语义靠非零初值（无效解标记）表达，"不超过"语义靠全零初值表达。

五、复杂度与适用前提

以二维 DP 表述，四个问题的时间复杂度均为 O(n × cap)（零钱兑换系列为 O(n × amt)），空间复杂度 O(n × cap)，空间优化后降为 O(cap)。从源码结构看，所有参考实现都未对"物品重量/硬币面值为 0"等非法输入做额外校验，使用时需保证 wgt[i] ≥ 1、coins[i] ≥ 1；零钱兑换 I 的 amt + 1 无效解技巧依赖"硬币数最多为 amt"的上界，要求存在面值为 1 的硬币时才总能凑出（否则最终返回 -1，行为正确）。

以上实现均在仓库各语言目录中提供了等价版本（如 codes/cpp/chapter_dynamic_programming/），可对照阅读以验证不同语言下同一套 DP 模板的写法一致性。