111.零钱兑换
题目
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
- 输入：coins = [1, 2, 5], amount = 11
- 输出：3
-
解释：11 = 5 + 5 + 1 示例 2：
-
输入：coins = [2], amount = 3
- 输出：-1
示例 3：
- 输入：coins = [1], amount = 0
- 输出：0
思路
这题最通俗的理解是： - 你在凑钱，问“凑出指定金额，最少要拿几枚硬币”。 - 比如要凑 11 元，硬币有 1、2、5。 - 最省的方法其实是 5 + 5 + 1，一共 3 枚。
给你一些不同面额的硬币（无限供应），以及一个目标金额 amount，问：最少需要多少枚硬币才能凑出这个金额？ 如果无法凑出，返回 -1。
例如： - coins = [1, 2, 5]，amount = 11 → 最少需要 3 枚（5+5+1） - coins = [2]，amount = 3 → 无法凑出 → 返回 -1 - coins = [1]，amount = 0 → 0 枚
但计算机不会一眼看出最优解
计算机只会一个一个试，它怎么试呢？ 它从0块钱开始，一点点网上算。
第一步： 0块钱怎么凑？ 0 块钱不需要任何硬币 → 记作 0 张。
第二步：1 块钱怎么凑？
只能用 1 块硬币 → 1 张。
（不能用 2 块或 5 块，因为它们比 1 块大）
第三步：2 块钱怎么凑？ 用 1 块：先凑 1 块（需要 1 张），再给 1 块 → 总共 2 张。 用 2 块：直接给 2 块 → 1 张。 选少的 → 1 张。 第四步：3 块钱怎么凑？ 用 1 块：先凑 2 块（需要 1 张），再给 1 块 → 总共 2 张。 用 2 块：先凑 1 块（需要 1 张），再给 2 块 → 总共 2 张。 （不能用 5 块） 所以最少 2 张。 第五步：4 块钱怎么凑？ 用 1 块：先凑 3 块（2 张）+1 块 → 3 张。 用 2 块：先凑 2 块（1 张）+2 块 → 2 张。 最少 2 张。 第六步：5 块钱怎么凑？ 用 1 块：先凑 4 块（2 张）+1 块 → 3 张。 用 2 块：先凑 3 块（2 张）+2 块 → 3 张。 用 5 块：直接给 5 块 → 1 张。 最少 1 张。 ……
这样一直算到 11 块钱，你就会发现最少是 3 张（5+5+1）。
发现规律了吗？
每次算一个新金额时，你只需要看三种可能性： - 如果我最后给的是 1 块硬币，那么我需要先凑出 金额-1 的最少硬币数，再加 1。 - 如果我最后给的是 2 块硬币，那么我需要先凑出 金额-2 的最少硬币数，再加 1。 - 如果我最后给的是 5 块硬币，那么我需要先凑出 金额-5 的最少硬币数，再加 1。
然后从这三个结果里选最小的。
比如算 6 块钱： - 最后给 1 块 → 先凑 5 块（1 张）+1 = 2 张 - 最后给 2 块 → 先凑 4 块（2 张）+1 = 3 张 - 最后给 5 块 → 先凑 1 块（1 张）+1 = 2 张 选最小的 → 2 张（5+1 或 1+5）。
计算机怎么记住这些结果？
它用一个表格（就是代码里的 dp 数组），从 0 到 11，每个格子记录凑到这个金额需要的最少硬币数。
一开始，除了 0 以外，所有格子都填一个很大的数（比如 99），表示“还不知道怎么凑”。
然后从 1 开始，按上面的方法，一格一格填。
填到 11 的时候，如果格子里的数还是 99，就说明凑不出来（比如只有 2 块硬币，却要凑 3 块）。
状态转移方程
设 dp[i] 表示凑出金额 i 所需的最少硬币数。
那么对于每个硬币面额 coin，如果 coin ≤ i，则有一种可能：
dp[i] = min(dp[i], dp[i - coin] + 1)
意思是：如果我最后用一枚 coin 硬币，那么我只需要先凑出 i - coin 元（最少需要 dp[i - coin] 枚），再加上这一枚即可。
在所有可能的硬币中取最小值，就是 dp[i] 的最优解。
初始化 - dp[0] = 0（凑 0 元不需要硬币） - 其他 dp[i] 初始化为一个很大的数（比如 amount + 1），表示暂时不可达。
class Solution {
fun coinChange(coins: IntArray, amount: Int): Int {
// 如果目标金额是 0，不需要任何硬币
if (amount == 0) return 0
// dp[i] 表示凑出 i 元所需的最少硬币数
// 初始化为 amount + 1（一个不可能达到的值，因为最多用 amount 枚 1 元硬币）
val dp = IntArray(amount + 1) { amount + 1 }
// 凑出 0 元需要 0 枚硬币
dp[0] = 0
// 从 1 元开始，逐步计算到目标金额
for (i in 1..amount) {
// 尝试每一种硬币
for (coin in coins) {
// 硬币面额不能大于当前金额
if (coin <= i) {
// 如果用这枚硬币，则总硬币数 = dp[i - coin] + 1
// 取所有可能中的最小值
dp[i] = minOf(dp[i], dp[i - coin] + 1)
}
}
}
// 如果 dp[amount] 仍然是初始值，说明无法凑出，返回 -1
// 否则返回 dp[amount]
return if (dp[amount] > amount) -1 else dp[amount]
}
}
复杂度
- 时间复杂度: O(amount × n)外层循环 amount 次，内层循环遍历所有硬币（n 种），每次操作 O(1)。
- 空间复杂度: O(amount)只使用了一个长度为 amount+1 的一维数组。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!