LC322 - 硬币兑换

这道题类似背包问题，取或不取，也可取多个，可以用自底向上的动态规划解决，首先可以将递归式列出。

F(0) = 0;
F(n) = Min{F(n - a[0]), F(n - a[1]), F(n - a[2]), ... F(n - a[a.length - 1])} + 1;
其中a为硬币数组。

代码如下：

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins.length == 0 || coins == null) return -1;
        int[] dp = new int[amount+1];
        dp[0] = 0;
        for(int i=1; i<=amount; i++){
            int minCount = Integer.MAX_VALUE;
            for(int j=0; j<coins.length; j++){
                if(i >= coins[j] && dp[i - coins[j]] != -1){
                    minCount = Math.min(dp[i - coins[j]] + 1, minCount);
                }
            }
            if(minCount == Integer.MAX_VALUE){
                dp[i] = -1;
            }else {
                dp[i] = minCount;
            }
        }
        return dp[amount];
    }
}