Open youngyangyang04 opened 3 months ago
感觉好难想到啊 判断dp[j-coins[i]
@359702798
感觉好难想到啊 判断dp[j-coins[i]
都取max_value了,再+1肯定就溢出到min_value了
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];
}
}
为什么现在不讲二维dp解法了
https://www.programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html