算法:零钱兑换

问题

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

示例1

输入:coins = [1, 2, 5], amount = 11
输出:3 (5+5+1)

示例2

输入:coins = [2], amount = 3
输出:-1 (无法满足)

解决方案

暴力破解

暴力破解即穷举,把各种可能组成总金额的情况都匹配一遍,得到所有满足的组合,然后取硬币数量最少的那组。

实现思路

剩余金额减去当前使用的硬币金额
如果大于 0 ,继续使用硬币来组合;
如果等于 0 ,匹配完成,将当前组使用的硬币数与最小组合硬币数对比,取较小者;
如果小于 0 ,直接淘汰。

暴力破解分析

参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public int CoinChange(int[] coins, int amount)
{
// 如果输入的金额小于等于0,返回0
if (amount <= 0) return 0;

// 设置初始值为 amount + 1,实际不存在这种情况的,最坏的情况是 amount
var minCount = amount + 1;

for (int i = 0; i < coins.Length; i++)
{
Cal(amount, coins, coins[i], new List<int>(), ref minCount);
}
return minCount == amount + 1 ? -1 : minCount;
}

public void Cal(int amount, int[] coins, int coin, List<int> curCoins, ref int minCount)
{
// 剩余金额-使用的硬币金额, 得到新的剩余金额
var leftAmount = amount - coin;

// 如果等于0,说明找到了一组满足的组合
if (leftAmount == 0)
{
curCoins.Add(coin);

// 如果当前组使用的硬币数量小于当前最小组合的硬币数量,重置最小值
if (curCoins.Count < minCount)
{
minCount = curCoins.Count;
}
}
// 如果剩余金额大于0,说明还继续获取新的硬币加入集合
else if (leftAmount > 0)
{
// 如果当前组的总硬币数量已经大于当前最小组合的硬币数量,就不需要在往下找了
if (curCoins.Count >= minCount)
{
return;
}

// 继续下一次
for (int i = 0; i < coins.Length; i++)
{
var newCoins = new List<int>(curCoins);
newCoins.Add(coin);
Cal(leftAmount, coins, coins[i], newCoins, ref minCount);
}
}
}
结论

从上图可以看出,获得所有可能组合的路线情况非常多,当 amount 值较小时复杂度还不算明显,随着 amount 越大,路线的深度(对应代码递归深度)会指数级增加(时间复杂度:2^n),所以当 amount 较大时这种方式必然不可取。

贪心

一般的贪心算法是先使用大币值,超界了就改用小币值,币值递减。

本题的币值是 [1,2,5],必然能用 2 肯定不会用 1,所以贪心没问题。但如果币值是 [1,5,6],当要组合总金额为 20 ,按贪心大币值的方式 6×3+1×2 = 20,需要使用 5 个硬币,而如果直接使用 5×4 = 20 只需要 4 个硬币,所以贪心并不合适,这里就先放弃该方案了。

动态规划
实现思路

定义 dp[i](dp[0] = 0)为组合成 i 时需要的最少硬币数,那么继续向前推就是 dp[i] = dp(i - coin[j]) 需要最少硬币数 + 1, + 1 是代表使用 coin[j] 算一次。

假设 i = 1:
当使用1币值组合,既 dp[1] = dp[0] + 1;

假设 i = 2:
当使用1币值组合,既 dp[2] = dp[1] + 1;
当使用2币值组合,既 dp[2] = dp[0] + 1;

假设 i = 3:
当使用1币值组合,既 dp[3] = dp[2] + 1;
当使用2币值组合,既 dp[3] = dp[1] + 1;

……

假设 i = 6:
当使用1币值组合,既 dp[6] = dp[5] + 1;
当使用2币值组合,既 dp[6] = dp[4] + 1;
当使用5币值组合,既 dp[6] = dp[1] + 1;

最终 dp[6] 取值为这 3 种情况的最小值。

动态规划的思路是将大问题化为子问题来解决,然后逐渐往大递推,所以得到最终的动态规划方程式为: dp[i] = Math.Min(dp[i], dp[i - coins[j]] + 1),dp[i] 的值可能会随着 coins[j] 不同而改变,所以需要将 dp[i] 和 dp[i - coins[j]] + 1 中较小值重新赋给 dp[i]。

参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int CoinChange(int[] coins, int amount)
{
var dp = new int[amount + 1];
// dp[0] 为 0,其他默认为 amount + 1(实际是不可能的),为了方便取对比结果中的最小值
for (int i = 1; i < dp.Length; i++)
{
dp[i] = amount + 1;
}

// 计算 1~amount 每项 dp[i] 的值
for (int i = 1; i <= amount; i++)
{
for (int j = 0; j < coins.Length; j++)
{
// 如果i能使用存在的面额来组合,得到每种面值组合后的最小值
if (coins[j] <= i)
{
dp[i] = Math.Min(dp[i], dp[i - coins[j]] + 1);
}
}
}

// 如果 dp[amount] 是 amount + 1 ,代表没找到组合结果,否则返回组合成 amount 需要的最少硬币数 dp[amount]
return dp[amount] > amount ? -1 : dp[amount];
}
总结

动态规划相比于暴力破解的方式就显得非常清晰、简洁了,它的时间复杂度是 O(amount×coins.length),核心点在于动态规划方程式的定义。

参考链接

如果对你有帮助就好