322. Coin Change - jiejackyzhang/leetcode-note GitHub Wiki

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.

解题思路为Dynamic Programming。

令dp[i]表示amount为i时所用coins的最小个数。 则对于coin n来说，可以取，也可以不取，因此：

dp[i] = min(dp[i], dp[i-n]+1）

这里我们首先要初始化dp[i]为一个较大的值max，例如amount+1。

base case为dp[0] = 0，即amount为0时，我们一个coin也不取。

最后若dp[amount] == max，则表示无法得到这个amount。

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[max];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++) {
            for(int n : coins) {
                if(n <= i) {
                    dp[i] = Math.min(dp[i], dp[i-n]+1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
}