零钱兑换 II

怎样从“coins=[1,2,5],amount=5 组合方式数 4。”推导出 背包 DP · 组合数，并证明每次状态变化都不会漏掉答案？

中心结论：完全背包计数 dp[j]+=dp[j-coin]。

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。题目数据保证结果符合 32 位带符号整数。

在本站主例中，coins=[1,2,5],amount=5 组合方式数 4。

算法最终需要得到或观察：4 种组合。

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 dp 计数数组。
3. 3转移每一步按照 完全背包计数 dp[j]+=dp[j-coin]。
4. 4收尾读取 4 种组合。，并复核边界与复杂度。

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：dp 计数数组。

此题虽然名字叫 Coin Change，但是不是经典的背包九讲问题。题目中 coins 的每个元素可以选取多次，且不考虑选取元素的顺序，因此这道题实际需要计算的是选取硬币的组合数。定义 dp[i] 表示金额之和等于 i 的硬币组合数，目标求 dp[amount]。初始边界条件为 dp[0] = 1，即不取任何硬币，就这一种取法，金额为 0 。状态转移方程 dp[i] += dp[i-coin]，coin 为当前枚举的 coin。 可能有读者会有疑惑，上述做法会不会出现重复计算。答案是不会。外层循环是遍历数组 coins 的值，内层循环是遍历不同的金额之和，在计算 dp[i] 的值时，可以确保金额之和等于 i 的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。 和此题完全一致的解题思路的题有，第 377 题和第 494 题。

完全背包计数 dp[j]+=dp[j-coin]。

执行过程中持续维护：dp 计数数组。

正确性依赖以下不变量：顺序无关,硬币外层循环。

面试时可以压缩为：完全背包计数 O(coins·amount)。

落到当前题，执行机制可以压缩为：完全背包计数 dp[j]+=dp[j-coin]。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入coins=[1,2,5],amount=5 组合方式数 4。 因为：完全背包计数 dp[j]+=dp[j-coin]。
2. 2固定硬币 1, 从金额 1 正序扫到 5先固定一种硬币,再看它能给哪些金额贡献新的组合。 因为：外层按硬币面额推进,组合只能按固定硬币顺序被生成一次,不会把 1+2 和 2+1 重复计算。
3. 3硬币 1, 金额 2: 0 + 1 = 1把 1 种“凑 1”的组合各追加一枚 1,并入原来 0 种“凑 2”的组合。 因为：因为当前行只允许使用已经处理过的硬币,新增组合一定以当前硬币作为最后加入的硬币,不会产生排列重复。
4. 4硬币 1, 金额 4: 0 + 1 = 1把 1 种“凑 3”的组合各追加一枚 1,并入原来 0 种“凑 4”的组合。 因为：因为当前行只允许使用已经处理过的硬币,新增组合一定以当前硬币作为最后加入的硬币,不会产生排列重复。
5. 5硬币 2, 金额 2: 1 + 1 = 2把 1 种“凑 0”的组合各追加一枚 2,并入原来 1 种“凑 2”的组合。 因为：因为当前行只允许使用已经处理过的硬币,新增组合一定以当前硬币作为最后加入的硬币,不会产生排列重复。
6. 6硬币 2, 金额 4: 1 + 2 = 3把 2 种“凑 2”的组合各追加一枚 2,并入原来 1 种“凑 4”的组合。 因为：因为当前行只允许使用已经处理过的硬币,新增组合一定以当前硬币作为最后加入的硬币,不会产生排列重复。
7. 7硬币 5, 金额 5: 3 + 1 = 4把 1 种“凑 0”的组合各追加一枚 5,并入原来 3 种“凑 5”的组合。 因为：因为当前行只允许使用已经处理过的硬币,新增组合一定以当前硬币作为最后加入的硬币,不会产生排列重复。
8. 8收尾与复杂度4 种组合。 因为：时间 O(coins·amount) · 空间 O(amount)。完全背包计数 dp[j]+=dp[j-coin]。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1
	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			dp[i] += dp[i-coin]
		}
	}
	return dp[amount]
}

func main() {
    // 1. 主例
    //    输入：mode="coin-change-combinations", coins=[1,2,5], amount=5
    //    期望：4 种组合。
    //
    // 2. 失败 / 未命中
    //    检查：与排列不同,内外循环顺序固定。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC322 最少硬币；LC377 组合总和 IV
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意coins=[1,2,5],amount=5 组合方式数 4。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化完全背包计数 dp[j]+=dp[j-coin]。
4. 4证明顺序无关,硬币外层循环。
5. 5复杂度时间 O(coins·amount)，空间 O(amount)