硬币找零问题

硬币找零问题(Coin Change)

Question

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.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

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

DP求解

如果是用DP求解，那么思路首先就是找到子问题。子问题很容易确定，那就是amount-x是子问题的amount。比较容易想到的代码实现如下：

public int coinChange(int[] coins, int amount) {
        if (amount == 0)
            return 0;
        int n = amount + 1; // the answer must smaller than [amount+1], nice!
        for (int coin : coins) {
            int curr = 0;
            if (amount >= coin) {
                int next = coinChange(coins, amount - coin);
                if (next >= 0)
                    curr = 1 + next;
            }
            if (curr > 0)
                n = Math.min(n, curr);
        }
        return (n == amount + 1) ? -1 : n;
    }

上述算法的时间复杂度为O(c^n),c是coin的数量，n是amount的值。

时间复杂度较大的原因是，中间存在很多重复计算。那么需要用到DP的备忘录，不用全局变量来保存计算过的值，也不用递归的方法来实现，而是只用一个一维数组，再用循环来实现。代码如下：

public 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] = amount + 1;
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i && minNumber[i - coins[j]] != amount + 1)
                    minNumber[i] = Integer.min(minNumber[i], 1 + minNumber[i - coins[j]]);
            }
        }
        if (minNumber[amount] == amount + 1)
            return -1;
        else
            return minNumber[amount];
    }