[Vssue]0322.零钱兑换.md

[youngyangyang04]

https://www.programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html

[359702798]

感觉好难想到啊 判断dp[j-coins[i]

[Du1in9]

@359702798

感觉好难想到啊 判断dp[j-coins[i]

都取max_value了，再+1肯定就溢出到min_value了

[Du1in9]

class Solution {
    public int coinChange(int[] coins, int w) {
        int[] dp = new int[w + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= w; j++) {
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if (dp[w] == Integer.MAX_VALUE) return -1;
        else return dp[w];
    }
}