LeetCode 热题100-80-零钱兑换

核心思想：动态规划
思路：
dp式：
dp[i]=min(dp[i],dp[i-coins[j]])

class Solution {

    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        int[] dp = new int[amount + 1];
        //每个数字的操作次数不会超过数字本身
        Arrays.fill(dp, amount + 1);
        //初始化条件
        dp[0] = 0;
        //从1-amount都遍历一遍
        for(int i = 1; i <= amount; i++){
        	//每次遍历时，把每个银币都使用一遍
            for(int j = 0; j < len; j++){
                if(coins[j] <= i){
                	//由于i - coins[j]，所以一定加起来等于i
                	//没有加起来等于i的，会使得dp[i]=amount+1
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        //如果dp[amount]=amount+1.则没有和为amount得排列组合
        return dp[amount] > amount ? -1 : dp[amount];
    }
}