零钱兑换

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

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

思路：dp[amount]，计算每个amount的关于提供硬币的所需硬币数量：针对提供的硬币数组，计算从0～amount的dp数组。存在这样的关系：

• 需要计算每一个金额最小的硬币数
• 遍历每一个硬币，如果可以大于要组成的amount，直接continue（无法通过这个硬币组成该金额）
• 小于amount，组成amount的硬币个数为：dp[amount - coinAmount] + 1（需要注意，如果dp[amount - coinAmount] 为-1，即无法组成该amount硬币组合，直接continue）
• 对于每种组合，求最小的进行赋值：dp[amount] = min(dp[amount - coinAmount] ) + 1

代码：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for(int am = 1; am <= amount; am++) {
            Integer count = null;
            for(int coin : coins) {
                int other = am - coin;
                if(other < 0) {
                    // 如果硬币面值过大，直接丢弃这种组合方式
                    continue;
                }else{
                    // 表示没有这种组合方式，丢弃
                    if(dp[other] == -1) {
                        continue;
                    }
                    // 首次直接赋值，后续需要取较小值更新
                    count = count == null ? dp[other] + 1 : Math.min(count,dp[other] + 1);
                }
            }
            dp[am] = count == null ? -1 : count;

        }
        return dp[amount];
    }
}