算法：零钱兑换
给定不同面额的硬币(coins)和一个总金额(amount) 。写一个函数来计算可以凑成总金额所需的最少的硬币个数，如果没有任何一种硬币组合能满足，返回 -1。
示例1
输入：coins = [1, 2, 5], amount = 11
输出：3 (5+5+1)
示例2
输入：coins = [2], amount = 3
输出：-1 (无法满足)
解决方案
暴力破解
暴力破解即穷举，把各种可能组成总金额的情况都匹配一遍，得到所有满足的组合，然后取硬币数量最少的那组。
实现思路
剩余金额减去当前使用的硬币金额
如果大于 0 ，继续使用硬币来组合；
如果等于 0 ，匹配完成，将当前组使用的硬币数与最小组合硬币数对比，取较小者；
如果小于 0 ，直接淘汰。
参考代码
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(), ref minCount);
}
return minCount == amount + 1 ? -1 : minCount;
}
public void Cal(int amount, int[] coins, int coin, List 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(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]。
参考代码
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];
}
About The Author
bjmayor
程序员，码农，php,python,ios,android,go，产品经理，创业。