零钱兑换

怎样从“coins=[1,2,5],amount=11 最少硬币 3(5+5+1)。”推导出 背包 DP · 零钱，并证明每次状态变化都不会漏掉答案？

中心结论：dp[a]=min(dp[a-c]+1);dp[0]=0,不可达 INF。

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

在本站主例中，coins=[1,2,5],amount=11 最少硬币 3(5+5+1)。

算法最终需要得到或观察：最少 3 枚。

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

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

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 dp 金额、硬币 c。
3. 3转移每一步按照 dp[a]=min(dp[a-c]+1);dp[0]=0,不可达 INF。
4. 4收尾读取 最少 3 枚。，并复核边界与复杂度。

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

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：dp 金额、硬币 c。

给出一些硬币和一个总数，问组成这个总数的硬币数最少是多少个？ 这一题是经典的硬币问题，利用 DP 求解。不过这一题的测试用例有一个很大的值，这样开 DP 数组会比较浪费空间。例如 [1,1000000000,500000] 有这样的硬币种类，要求组成 2389412493027523 这样的总数。那么按照下面的解题方法，数组会开的很大，非常浪费空间。这个时候用 DFS 解题会节约一点空间。

dp[a]=min(dp[a-c]+1);dp[0]=0,不可达 INF。

执行过程中持续维护：dp 金额、硬币 c。

正确性依赖以下不变量：完全背包最值:每种硬币无限。

面试时可以压缩为：DP O(amount·coins)。

落到当前题，执行机制可以压缩为：dp[a]=min(dp[a-c]+1);dp[0]=0,不可达 INF。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入coins=[1,2,5],amount=11 最少硬币 3(5+5+1)。 因为：dp[a]=min(dp[a-c]+1);dp[0]=0,不可达 INF。
2. 2dp[1] 用硬币 1: 0+1 = 1尝试每种硬币松弛。 因为：完全背包正序枚举容量。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4dp[3] 用硬币 1: 1+1 = 2尝试每种硬币松弛。 因为：完全背包正序枚举容量。
5. 5dp[4] 用硬币 2: 1+1 = 2尝试每种硬币松弛。 因为：完全背包正序枚举容量。
6. 6dp[5] 用硬币 5: 0+1 = 1尝试每种硬币松弛。 因为：完全背包正序枚举容量。
7. 7无法凑出返回 dp[amount]。 因为：O(amount·|coins|)。
8. 8收尾与复杂度最少 3 枚。 因为：时间 O(amount·coins) · 空间 O(amount)。dp[a]=min(dp[a-c]+1);dp[0]=0,不可达 INF。

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

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	dp[0] = 0
	for i := 1; i < len(dp); i++ {
		dp[i] = amount + 1
	}
	for i := 1; i <= amount; i++ {
		for j := 0; j < len(coins); j++ {
			if coins[j] <= i {
				dp[i] = min(dp[i], dp[i-coins[j]]+1)
			}
		}
	}
	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func main() {
    // 1. 主例
    //    输入：mode="coin-change", coins=[1,2,5], amount=11
    //    期望：最少 3 枚。
    //
    // 2. 失败 / 未命中
    //    检查：外层循环硬币/金额顺序影响完全背包。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC518 组合数；LC279 平方数
}

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

1. 1题意coins=[1,2,5],amount=11 最少硬币 3(5+5+1)。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化dp[a]=min(dp[a-c]+1);dp[0]=0,不可达 INF。
4. 4证明完全背包最值:每种硬币无限。
5. 5复杂度时间 O(amount·coins)，空间 O(amount)