322. Coin Change

Question

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return 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.

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

Solution

动态规划，首先将amount长度的数组填满最大值。
双重遍历数组和硬币，不取当前硬币的上一个状态加一（dp[i - coin]+1）就是当前可取的最小值。
注意先取硬币，将amount的起始值设置为硬币面值可以增快速度。（减少了面值大于总额的情况。）

Code

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