组成指定金额的最少硬币数量问题探讨

题目

给定不同面额的硬币 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];
    }
}