Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

例子1

coins = [1, 2, 5], amount = 11

return 3 (11 = 5 + 5 + 1)

例子2

coins = [2], amount = 3

return -1.

You may assume that you have an infinite number of each kind of coin.

题意：

零钱兑换，让你用最少的零钱数换取目标的数量

解题思路：DP

Let M[j] indicates the minimum number of coins required to make a change for j amount.

public static int coinChange(int[] coins, int amount) {
    if (coins == null || coins.length == 0 || amount <= 0)
        return 0;
    int[] minNumber = new int[amount + 1];

    for (int i = 1; i <= amount; i++) {
        minNumber[i] = Integer.MAX_VALUE;
        for (int j = 0; j < coins.length; j++) {
            if (coins[j] <= i && minNumber[i - coins[j]] != Integer.MAX_VALUE)
                minNumber[i] = Integer.min(minNumber[i], 1 + minNumber[i - coins[j]]);
        }
    }

    if (minNumber[amount] == Integer.MAX_VALUE)
        return -1;
    else
        return minNumber[amount];
}

Follow Up

How many ways can we make the change

public void printCoinChangingSolution(int total,int coins[]){
    List<Integer> result = new ArrayList<>();
    printActualSolution(result, total, coins, 0);
}

private void printActualSolution(List<Integer> result,int total,int coins[],int pos){
        if(total == 0){
            for(int r : result){
                System.out.print(r + " ");
            }
            System.out.print("\n");
            return;
        }

        for(int i=pos; i < coins.length; i++){
            if(total >= coins[i]){
                result.add(coins[i]);
                printActualSolution(result,total-coins[i],coins,i);
                result.remove(result.size()-1);
            }
        }
}

References

1 Dynamic Programming — Coin Change Problem

2 CoinChanging.java from Mission Peace

3 Coin Change from leetcode