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.

Thinking:

In order to solve this problem, we can use dp which check whether choose current coin to make sure it’s minimum. But using function recursively will waste a lot of time. So we need to use extra space avoiding waste time. Then, we should build up a dp array accroding to the amount of money. Then update the dp value of different amout from zero to the target amout. The DP expression is: dp[i + coins[j]] = Math.min(dp[i + coins[j]], dp[i] + 1)

Solution:

public int coinChange(int[] coins, int amount) {
    int dp[] = new int[amount + 1];
    for (int i = 1; i <= amount; i++) dp[i] = Integer.MAX_VALUE-1;
    for (int i = 0; i <= amount; i++) {
        for (int j = 0; j < coins.length; j++) {
            if (i + coins[j] <= amount)
                dp[i + coins[j]] = Math.min(dp[i + coins[j]], dp[i] + 1);
        }
    }
    return dp[amount] == Integer.MAX_VALUE-1 ? -1 : dp[amount];
}