322. 零钱兑换
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
这句话结合本题 大家要好好理解。
视频讲解：https://www.bilibili.com/video/BV14K411R7yv
https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 0;
for(int i = 1; i <= amount; i ++){
dp[i] = 10001;
}
for(int i = 0; i < coins.length; i ++){
for(int j = coins[i]; j <= amount; j ++){
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
if(dp[amount] == 10001) return -1;
return dp[amount];
}
}
279.完全平方数
本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做
视频讲解：https://www.bilibili.com/video/BV12P411T7Br
https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html
class Solution {
public int numSquares(int n) {
int num = 0;
while(num*num <= n){
num ++;
}
int[] item = new int[num];
for(int i = 0; i < num; i ++){
item[i] = i * i;
}
int[] dp = new int[n + 1];
for(int i = 0; i <= n; i ++){
dp[i] = Integer.MAX_VALUE;
}
dp[0] = 0;
for(int i = 1; i < num; i ++){
for(int j = item[i]; j <= n; j ++){
if(dp[j - item[i]] != Integer.MAX_VALUE){
dp[j] = Math.min(dp[j], dp[j - item[i]] + 1);
}
}
}
return dp[n]==Integer.MAX_VALUE?-1:dp[n];
}
}
139.单词拆分
视频讲解：https://www.bilibili.com/video/BV1pd4y147Rh
https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordset = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for(int j = 0; j <= s.length(); j ++){
for(int i = 0; i < j; i ++){
if(wordset.contains(s.substring(i, j)) && dp[i]) dp[j] = true;
}
}
return dp[s.length()];
}
}
关于多重背包，你该了解这些！
背包问题总结篇！
https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html
