在昨天的文章关于背包问题的一点发散之后，有小伙伴说感觉跟LeetCode上一道题零钱兑换很像，但是又好像有点不一样，简单的暴力递归跟缓存优化都能做出来，就是自下而上的方法不怎么有思路。我看了下，其实这道题跟我们昨天的题目有异曲同工之处，可以说极度相似，今天我们就来分析分析这道题。
题目我再贴出来：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
我们来看两个例子：
输入: coins = [1, 2, 5], amount = 11 输出: 3
输入: coins = [2], amount = 3 输出: -1
每次遇到这样的问题我们总是本能地用暴力递归来做，没有问题，先实现，后期优化，跟随自己的想法来。暴力递归无需过多分析了，无非是递归地做选择，选择硬币，然后选择硬币最少的那个方案。
咱们直接上递归代码，咱们主要思考分析工作在后期的算法优化上。
public int countChange(int[] denominations, int total) {
int result = this.countChangeRecursive(denominations, total, 0);
return (result == Integer.MAX_VALUE ? -1 : result);
}
private int countChangeRecursive(int[] denominations, int total, int currentIndex) {
if (total == 0)
return 0;
if (denominations.length == 0 || currentIndex >= denominations.length)
return Integer.MAX_VALUE;
// 不停地做选择，只要当前面值比剩余数目小，我们都可以选择这个硬币
int count1 = Integer.MAX_VALUE;
if (denominations[currentIndex] <= total) {
int res = countChangeRecursive(denominations, total - denominations[currentIndex], currentIndex);
if (res != Integer.MAX_VALUE) {
count1 = res + 1;
}
}
// 直接跳过当前面值，进行下一次选择
int count2 = countChangeRecursive(denominations, total, currentIndex + 1);
return Math.min(count1, count2);
}
这边由于是选择可以的最小数目，所以我们把边界条件设置成Integer的最大值。这个时间复杂度也很容易看出来了，是O(2^(T+C))。T是需要换零的总数额，C是硬币种类数量。
写到这里我们就可以做第一步优化了，这是我们第四次讨论这样的题目了，基本上可以判断通过缓存可以把算法复杂度进一步优化。每次做选择的时候，变化的只有剩余需要换零数额跟当前硬币的索引，所以我们可以用一个二维数组来存储已经算得的结果。
public int countChange(int[] denominations, int total) {
Integer[][] dp = new Integer[denominations.length][total + 1];
int result = this.countChangeRecursive(dp, denominations, total, 0);
return (result == Integer.MAX_VALUE ? -1 : result);
}
private int countChangeRecursive(Integer[][] dp, int[] denominations, int total, int currentIndex) {
if (total == 0)
return 0;
if(denominations.length == 0 || currentIndex >= denominations.length)
return Integer.MAX_VALUE;
// 如果之前已经遇到过同样场景，直接返回结果
if(dp[currentIndex][total] == null) {
// 只要当前硬币面额比剩余需换零数目小，我们就可以考虑用它来换零
int count1 = Integer.MAX_VALUE;
if( denominations[currentIndex] <= total ) {
int res = countChangeRecursive(dp, denominations, total - denominations[currentIndex], currentIndex);
if(res != Integer.MAX_VALUE){
count1 = res + 1;
}
}
// 直接跳过当前面额，去选择其他面额
int count2 = countChangeRecursive(dp, denominations, total, currentIndex + 1);
dp[currentIndex][total] = Math.min(count1, count2);
}
return dp[currentIndex][total];
}
相信这两步对大家都没什么难度，大家可以很轻松地做到这一步。我们直接来思考一下自下而上的方式，我们该怎么做。
本质上，遇到任何面值的硬币，对于任何需要换零的数目，我们都想用最少的硬币来完成。那么对于所有可能的total ‘t’ (0<= t <= 总的换零数目) 和所有可能的硬币index (0 <= index < 硬币种类数目)，我们有两种选择：
- 跳过当前面额的硬币，那么此时我们可以得到的最小硬币数就是
dp[index-1][t]。 - 当前硬币面额小于需要换零额度时，我们就用它来换零，在这种情况下，我们就需要拿到能换到剩余数额的最小硬币数。那此时的最小硬币数就是
dp[index][t-denominations[index]] + 1。
最终，我们的最小硬币数一定是这两种选择中最小的那一个。dp[index][t] = min(dp[index-1][t], dp[index][t-denominations[index] + 1)。可能光这么说有点抽象，我们来具体点。
假使面值: [1, 2, 3] 换零总额: 7。
零钱兑换
原谅我不会画表格，当我们只有面值为一的硬币时，我们要还多少钱就要多少个硬币。当我们有面值为1，2两种的硬币时，当我们对5进行兑换时，不选择2这个面值的话，dp[0][5]是5，也就是我们需要5个面值为1的硬币，而dp[1][3]是是2，那这种情况兑换硬币就只要3个。最终兑换5所需最少硬币数就是3.
好了，思路都解释清楚了，剩下来的就是代码实现了。
public int countChange(int[] denominations, int total)
{
int n = denominations.length;
int[][] dp = new int[n][total + 1];
for(int i=0; i < n; i++)
for(int j=0; j <= total; j++)
dp[i][j] = Integer.MAX_VALUE;
// 换零金额是0的时候需要的硬币当然为0
for(int i=0; i < n; i++)
dp[i][0] = 0;
for(int i=0; i < n; i++) {
for(int t=1; t <= total; t++) {
if(i > 0)
dp[i][t] = dp[i-1][t]; //不选择当前硬币
if(t >= denominations[i]) {
if(dp[i][t-denominations[i]] != Integer.MAX_VALUE)
dp[i][t] = Math.min(dp[i][t], dp[i][t-denominations[i]]+1); // 西安则当前硬币
}
}
}
// 最佳答案照例出现在最角落里
return (dp[n-1][total] == Integer.MAX_VALUE ? -1 : dp[n-1][total]);
}
哎，好了，这时候的复杂度就只有O(T*C)了，这么一看，我们这道题其实还是很简单的，LeetCode很多题目的题面本身都已经暗示我们要用什么方法来解题了，只要努力把它转化成我们熟悉的题目，往我们会的思路上靠就可以了。
网友评论