零钱兑换

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

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

示例 2:

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

说明:

• 你可以认为每种硬币的数量是无限的。

动态规划解法：

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins.length == 0)
            return -1;
        if(amount <= 0)
            return 0;
        Arrays.sort(coins);
        int[] dp = new int[amount+1];
        dp[0] = -1;
        for(int i = 1;i<=amount;i++){
            int minCount = Integer.MAX_VALUE;
            for(int j=coins.length-1;j>=0;j--){
                int tmp = coins[j];
                if(tmp <= i){
                    //取余数
                    int rem = i%tmp;
                    if(rem == 0){
                        //整除
                        minCount = Math.min(minCount,i/tmp);
                    }else{
                        //没有整除
                        int count = i/tmp;
                        while(count > 0){
                            //取余数
                            rem = i - count*tmp;
                            if (dp[rem] != -1){
                                minCount = Math.min(minCount,dp[rem]+count);
                            }
                            count--;
                        }
                    }
                }
            }
            if(minCount == Integer.MAX_VALUE){
                dp[i] = -1;
            }else{
                dp[i] = minCount;
            }
        }
        return dp[amount];
    }
}