image.png

解法

class Solution {
    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        // amount为j时，最少的硬币个数
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        dp[0] = 0;
        for (int i = 0; i < len; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                // 取coins[i]时，在以前解法的基础上加1，不取就用之前的数目
                dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);                    
            }
        }
        if (dp[amount] >= Integer.MAX_VALUE - 1) {
            return -1;
        }
        return dp[amount];        
    }
}