Hello 算法：零钱兑换 II 的动态规划与空间优化——Python Tutor 可视化版本源码解读

本文以 hello-algo 仓库中 codes/pythontutor/chapter_dynamic_programming/coin_change_ii.md 为主体，完整还原该文件内嵌的两段 Python 实现——二维动态规划 coin_change_ii_dp 与空间优化后的 coin_change_ii_dp_comp，逐行讲清“零钱兑换 II”（统计凑出目标金额的硬币组合数量）的状态定义、初始化、状态转移与降维技巧，并对照 Python 源码 与 动态规划章节文档 给出复杂度分析与多语言实现索引，读完即可独立复现该算法并理解两种实现版本的全部差异。

文件定位：pythontutor 目录是算法代码的可视化伴生文件

codes/pythontutor/ 目录按章节组织（chapter_array_and_linkedlist、chapter_backtracking、chapter_computational_complexity、chapter_divide_and_conquer、chapter_dynamic_programming、chapter_graph、chapter_greedy、chapter_hashing、chapter_heap、chapter_searching、chapter_sorting、chapter_stack_and_queue、chapter_tree），每个 .md 文件是仓库 Python 实现的“可视化伴生文件”。以本文的 coin_change_ii.md 为例，其结构非常规整：

1. 文件头注释：标注文件名 coin_change_ii.md、创建时间 2024-01-05、作者 krahets；
2. 两条 HTML 注释：每条注释先以 [file]{coin_change_ii}-[class]{}-[func]{coin_change_ii_dp}（或 coin_change_ii_dp_comp）标识对应的源文件与函数，随后跟随一条 Python Tutor 的 render.html 可视化链接。链接的 code= 参数经 URL 编码，解码后就是完整的可运行 Python 代码（含函数与驱动代码），可在 Python Tutor 在线环境中逐步查看变量与 dp 表的内存变化。

可以确认，文件中两段编码链接解码后的代码与 codes/python/chapter_dynamic_programming/coin_change_ii.py 逐行一致（后者额外把两个函数合并在同一文件中）。因此本文件承担的角色是：把动态规划算法的每一次 dp 表更新过程“可视化”，供读者观察状态转移的执行轨迹。

问题定义：从“最少硬币数”到“组合数量”

“零钱兑换 II”在 动态规划章节文档 中的表述是：给定 $n$ 种硬币，第 $i$ 种硬币面值为 $coins[i-1]$，目标金额为 $amt$，每种硬币可重复选取，求凑出目标金额的硬币组合数量。它与“零钱兑换 I”（求最少硬币数）同属完全背包类问题，区别仅在于子问题从“最少数量”变为“方案计数”，因此状态转移从取最小值变为求和。

文档给出的状态转移方程为：

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

即“前 $i$ 种硬币凑出金额 $a$ 的组合数 = 不选硬币 $i$ 的组合数 + 选硬币 $i$ 的组合数”。下文两段代码正是该方程的两种存储形式。

版本一：二维动态规划 coin_change_ii_dp

这是 pythontutor 文件第一条链接内嵌的代码（对应 coin_change_ii.py 第 8–25 行），完整继承如下：

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]

逐点解析：

• dp 表规模：(n + 1) × (amt + 1) 的二维矩阵。dp[i][a] 定义为“仅使用前 $i$ 种硬币，凑出金额 $a$ 的组合数量”，下标 i 从 1 计到 $n$，故第 0 行表示“无硬币可用”，天然为 0，无需单独初始化。
• 首列初始化 dp[i][0] = 1：金额为 0 时无须选择任何硬币即已凑成，对任意 $i$ 都恰好有 1 种方案（“空选择”）。这是计数类 DP 与求最值类 DP 的关键差异——coin_change 的 dp 表 首列是 0（0 元不需要硬币），而本题首列是 1。
• 转移的分支结构：
  • 当 coins[i-1] > a（当前硬币面额大于目标金额）时，选它必然超支，只能继承上一行 dp[i-1][a]，即“不选硬币 i”；
  • 否则执行完整转移 dp[i-1][a] + dp[i][a - coins[i-1]]。注意第二项使用的是当前行 dp[i][...] 而非 dp[i-1][...]，这正是“可重复选取”的体现：选过一次硬币 $i$ 后，剩余金额仍允许继续选硬币 $i$。这与 完全背包问题 的转移形式一致。
• 返回值：dp[n][amt]，即使用全部 $n$ 种硬币凑出 $amt$ 的方案总数。

版本二：空间优化 coin_change_ii_dp_comp

pythontutor 文件第二条链接内嵌的是降维版本（对应 coin_change_ii.py 第 28–44 行）：

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]

降维的原理与细节：

• 删除硬币维度：观察二维转移，dp[i][a] 只依赖 dp[i-1][a]（上一行）与 dp[i][a - coins[i-1]]（当前行更早的列）。当外层按硬币种类 $i$ 推进、内层对金额 a 正序遍历时，dp[a - coins[i-1]] 恰好是本轮已经用上了硬币 $i$ 的新值，dp[a] 自身则是“尚未更新”的旧值（语义上等价于 dp[i-1][a]）。于是二维表可压缩为一维 dp[a]，空间从 $O(n \cdot amt)$ 降到 $O(amt)$。
• 正序遍历不可颠倒：这里内层必须是正序。正序保证 dp[a - coins[i-1]] 包含当前硬币的贡献，等价于“同一种硬币可以重复选”，与二维版语义完全一致。若改成逆序，dp[a - coins[i-1]] 将保持旧值，语义就变成“每种硬币最多选一次”（0-1 背包形式），计数结果会错误地减少。这一点在 完全背包问题的空间优化 一节中被明确为与本题相同的处理方式。
• dp[a] = dp[a] 这一分支：当 coins[i-1] > a 时，二维版写 dp[i][a] = dp[i-1][a]（继承旧值）；降维后旧值仍在 dp[a] 原位，因此退化为一次自赋值。从源码结构看，作者特意保留该分支而非直接 pass，是为了让一维代码与二维代码的分支结构逐行对应，方便读者对照理解——这一结构在 Go 版本、Java 版本 等其他语言实现中同样存在。

驱动代码与结果验证

两段内嵌代码都附带相同的 Driver Code（对应 coin_change_ii.py 第 47–58 行）：

"""Driver Code"""
if __name__ == "__main__":
    coins = [1, 2, 5]
    amt = 5

    # 动态规划
    res = coin_change_ii_dp(coins, amt)
    print(f"凑出目标金额的硬币组合数量为 {res}")

    # 空间优化后的动态规划
    res = coin_change_ii_dp_comp(coins, amt)
    print(f"凑出目标金额的硬币组合数量为 {res}")

以 coins = [1, 2, 5]、amt = 5 手工验证，凑法恰有 4 种（不计顺序的组合）：

1. 5
2. 2 + 2 + 1
3. 2 + 1 + 1 + 1
4. 1 + 1 + 1 + 1 + 1

因此两个函数都应输出“凑出目标金额的硬币组合数量为 4”，可直接运行 codes/python/chapter_dynamic_programming/coin_change_ii.py 验证（仅需 Python 3.9+，使用了 list[int] 内置泛型语法，无第三方依赖）。

复杂度分析

• 两个版本的外层循环 $n$ 次、内层循环 $amt$ 次，每次转移为 $O(1)$，时间复杂度均为 $O(n \cdot amt)$；
• coin_change_ii_dp 的空间复杂度为 $O((n+1) \cdot (amt+1))$，coin_change_ii_dp_comp 压缩为 $O(amt)$；
• 适用前提：硬币面值为正整数、目标金额 $amt$ 非负。当 $amt = 0$ 时，二维版首列初始化使 dp[n][0] = 1，一维版 dp[0] = 1，均正确返回 1 种“空组合”。

仓库中的配套资源

• 文档讲解：docs/chapter_dynamic_programming/unbounded_knapsack_problem.md 的“零钱兑换问题 II”小节（约第 175–207 行）给出了本文完整推导——子问题定义、转移方程、首列初始化为 1 的原因，并引用了 [file]{coin_change_ii}-[func]{coin_change_ii_dp} 与 [func]{coin_change_ii_dp_comp} 两段代码，与 pythontutor 文件中的 [file]{}-[func]{} 标识一一对应；
• 多语言实现：同一题面在仓库内提供了 14 种语言版本，便于横向对照状态转移的写法差异：C、C++、C#、Dart、Go、Java、JavaScript、Kotlin、Python、Ruby、Rust、Swift、TypeScript、Zig；
• 同目录姊妹篇：coin_change.md 对应“零钱兑换 I”（求最少硬币数），其二维版首行用 MAX = amt + 1 表示“不可达”、转移取 min，与本文计数版的求和转移形成鲜明对照，建议对照阅读。

小结

codes/pythontutor/chapter_dynamic_programming/coin_change_ii.md 以“函数标识 + 编码链接”的形式，把零钱兑换 II 的两种动态规划实现送进了 Python Tutor 的逐步可视化环境：二维版 coin_change_ii_dp 完整保留了 (n+1) × (amt+1) 状态表与首列置 1 的初始化，一维版 coin_change_ii_dp_comp 则通过“外层遍历硬币、内层金额正序”的循环顺序，在不改变计数语义的前提下把空间降到 $O(amt)$。配合 Python 源码 与 章节文档 的推导，即可完整掌握“组合计数型完全背包”的状态定义、转移方程与空间优化三要素。