动态规划

public int coinChange(int[] coins, int amount) {
    int max = amount + 1;          //这里最大值为amount          
    int[] dp = new int[amount + 1];//dp[i]=j表示组成金额为i所需最少硬币为j
    Arrays.fill(dp, max);  
    dp[0] = 0;   
    for (int i = 1; i <= amount; i++) {  //遍历求dp
        for (int j = 0; j < coins.length; j++) { //遍历每一种硬币金额
            if (coins[j] <= i) {         //如果该硬币金额小于等于需要组成的金额
                //dp[i - coins[j]] + 1 表示使用该硬币组成
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    //判断是否发生了更新
    return dp[amount] > amount ? -1 : dp[amount];
}