组成指定金额的最少硬币数量问题探讨
题目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/gaM7Ch 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
硬币使用次数无限
其实这就是一个简单的背包问题，等同于塞满一个指定的背包所需要的最少物件。 例如要凑成总量为amount的金币。你可以先假想为放置的金币是有先后顺序的，那么你所放置的最后一枚金币，肯定存在于coins数组。因此，若能知晓填满amount-coins[i]所需的金币数量，你就可以递推出填满amount所需的金币数量。如果要取最少的数量，直接利用Math.max(dp[j],dp[j-coins[i]]+1)比较得出即可，又知题目要求金币可以无限用。
显然，在做动态规划的方程转移时。需要把金币循环放置在第二层。这样，才有反复使用的效果。
代码如下
class Solution {
public int coinChange(int[] coins, int amount) {
//金币的数量不可能超过amount+1
int max = amount + 1;
int[] dp = new int[amount + 1];
//因为涉及最小值比较，初始值必须设置为amount以上的数值，本例选取了amount+1
Arrays.fill(dp, max);
//凑满0不需要金币，因此是0
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
硬币只可以使用1次
如果硬币每次只能使用1次，那么，再将金币的循环放置在第二层显然是不可取的。因此金币的循环需要在外层。保证每种金币只使用一次。
此外，dp数组的初始值需要大于coins.length或者amount
最关键的问题就在于第二层循环，必须是倒序，因为顺序的话，根据转移方程，金币还是会被多次使用， 而采用倒序的方式，即可避免此问题
class Solution {
public int coinChange(int[] coins, int amount) {
int max = coins.length + 1;
int[] dp = new int[amount+1];
//因为涉及最小值比较，初始值必须设置为coins.length或amount以上的数值，本例选取了coins.length+1
Arrays.fill(dp, max);
//凑满0不需要金币，因此是0
dp[0] = 0;
for (int i = 0; i < coins.length; ++i) {
for (int j = amount; j >= coins[i] ; --j) {
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] > coins.length ? -1 : dp[amount];
}
}
硬币使用的次数有限
若题目除了给出coins外，再给出一个count数组，表示每种金币的数量，那么这种情况下如何求出组成amount金额所需的最少金币数量呢。
与此前的一次和无限次不同，此种情况给定了每种金币所使用次数的限制条件，因此，在做状态方程转移时，我们必须要知道当前金币所使用的数量，假设有状态转移方程dp[j]=dp[j-coins[i]]+1;表示我们现在使用了一枚面额为coins[i]的金币，可是，我们如何知道dp[j-coins[i]]里已经用了多少枚面额为coins[i]的金币呢？额外使用一个dp2数组维护是否可以？其实试试就不难发现，金币额的使用是无法简单用一个一维数组维护的，
请看如下代码。
public static int coinChange(int[] coins, int[] count, int amount) {
int max = coins.length + 1;
int[] dp = new int[amount+1];
int[] dp2=new int[amount+1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 0; i < coins.length; ++i) {
Arrays.fill(dp2,0);
for (int j = coins[i]; j <= amount ; ++j) {
if(dp[j-coins[i]]+1<dp[j]){
if(dp2[j-coins[i]]+1<=count[i]){
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
dp2[j]=dp2[j-coins[i]]+1;
}
}
}
}
return dp[amount] > coins.length ? -1 : dp[amount];
}
假设dp2表示当前循环所使用的金币的使用情况，例如coins={1,2,3}，count={10,10,2},aount=9;在循环到coins[2]时，此时循环dp[6]肯定等于2，而dp2[6]=2，表示金额为三的金币已经使用两次，在循环到dp[9]时，我们发现就不能再添加金额为3的金币了，因为其使用量已经达到上限，因而dp[9]只能使用循环coins[1]时的数值，其值为5，可是9可以拆分为3,3,2,1，只需要4枚。因而出错，按正确答案回推，dp[6]应该等于3，dp2[6]应该等于1，即1,2,3。显然，1,2,3在coins[2]循环中会被3,3替代。此方法不可行。
如果我们将dp表示成一个二维数组，行为金币的种类，列为amount。
第一行表示，如果现在没有金币，组成amount所需的金币最少数量，第二行表示，如果只有一种金币，组成amount所需的金币的最少数量.....以此递推，求出dp[coins.length][amount]。即为正确答案。
直接上代码。
class Solution {
public int coinChange(int[] coins, int[] count, int amount) {
//因为涉及最小值比较，初始值必须设置为amount以上的数值，本例选取了amount+1
int max = amount + 1;
int[][] dp = new int[coins.length+1][amount+1];
//初始化数组
for(int i = 0; i < coins.length+1; i++){
Arrays.fill(dp[i],max);
dp[i][0] = 0;
}
for (int i = 1; i <= coins.length; ++i) {
for (int j = 1; j <= amount ; ++j) {
if(j < coins[i-1]){
dp[i][j] = dp[i-1][j];
}else{
int top = Math.min(count[i-1],j/coins[i-1]);
int min = amount +1;
for( int k = 0; k <= top; ++k){
min = Math.min(min,dp[i-1][j-k*coins[i-1]]+k);
}
dp[i][j] = min;
}
}
}
return dp[coins.length][amount] > amount ? -1 : dp[coins.length][amount];
}
}
查看8道真题和解析