​LeetCode刷题实战322：零钱兑换

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

示例 4：

输入：coins = [1], amount = 1
输出：1

示例 5：

输入：coins = [1], amount = 2
输出：2

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