笔记：代码随想录算法训练营day38： LeetCode322. 零钱兑换、279.完全平方数、139.单词拆分；多重背包
学习资料：代码随想录
我可不可以把动规叫正溯或者前溯
求方法：放i 的方法加上不放i（空出位置）的方法
求值：max或者min 放或不放i（空出位置）
322. 零钱兑换
力扣题目链接
定义：dp[j]为凑成金额j需要的最少硬币个数
递推：按完全背包来，取的是最小值，weight为coins[i],value为1
初始化：取最小值，全都初始化为最大值，装的背包容量为0时，硬币个数也是0
遍历顺序：按多重背包来，求的是个数，先遍历谁都行
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<uint64_t> dp(amount+1,INT_MAX); //要找最小值，所以先都初始化为一个最大值
dp[0] = 0;
for(int i=0;i<coins.size();i++){
for(int j=0;j<=amount;j++){
if(j>=coins[i]&&dp[j-coins[i]]!=INT_MAX){ //值还为INT_MAX说明这一点就凑不出来
dp[j] = min(dp[j],dp[j-coins[i]]+1); //求的是个数，由此可把每一个value都看作是1
}
}
}
if(dp[amount]==INT_MAX) return -1;
return dp[amount];
}
};
279.完全平方数
力扣题目链接
思路：和上一题差不多，物品i的weight为i*i，value为1
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
dp[0] = 0;
for(int i=0;(i*i)<=n;i++){
for(int j=i*i;j<=n;j++){
if(dp[j-i*i]!=INT_MAX){ //其实是不会存在不能构成的情况了，因为有‘1’托底
dp[j] = min(dp[j],dp[j-i*i]+1); //复习一下递推公式是啥：是不放物品i和放物品i（把物品i让出来）的值的比较
}
}
}
return dp[n];
}
};139.单词拆分
力扣题目链接
对我来说理解起来有些难度了
定义：dp[j]表示s长度为j时是否能由字典里的单词组成
递推：如果s中的前j个长度中的某一段长度可以在字典中找到并且这一段长度之前的长度是true，那么这段长度也是true
初始化：长度为0时要定义为true，首先长度为0的s不会出现，这里就是单纯为了后边的推导，其余初始为false
遍历顺序：先背包后物品。 理解1：要找的是排列而不是组合，按多重背包求排列来。 理解2：要用字符串去字典里找单词才能看出来到底字符串是不是由这些单词组成的，否则拿着单词去翻字符串的话，找到一个一样的单词，后边的根据递推公式就跳过去了
举例：代码随想录"applepenapple", ''apple,pen''
假如先遍历单词了，因为j=0时用的是apple，在遍历到pen处dp[8]不会更新，所以在后面dp[13]又遇到apple了，还是不能正确更新，然后虽然在用pen遍历时dp[8]会更新，但不会再用apple遍历了，所以dp[13]还是false
// 五部曲
// 定义：dp[j]表示字符串长度为j时，是否可以由字典中出现的一个或多个单词组成
// 递推：if(s[j;i-1]可被字典拆分并且s[0:j-1]](前j个)可被字典拆分
// 初始化：dp[0]得是true，得往下推，而且s的长度>=1,没有空的s
// 遍历顺序，不同单词排列还是有区别，所以找排列，先遍历背包
// 打印
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size()+1,false);
unordered_set<string> wordSet(wordDict.begin(),wordDict.end());
dp[0] = true;
for(int j=0;j<=s.size();j++){
for(int i=0;i<j;i++){
string word = s.substr(i,j-i);
//if(find(wordDict.begin(), wordDict.end(), word) != wordDict.end() && dp[i]==true){ 这样时间复杂度就是O（n）了
if(wordSet.find(word)!=wordSet.end() && dp[i]==true){
dp[j] = true;
}
}
}
return dp[s.size()];
}多重背包
卡码网第56题
将有限的物品展开成多个物品使其变成01背包问题，但是展开不能在初始化之前展开，那样会超时，要在递推公式前的遍历时展开，相当于给每一种物品都打包了
#include <iostream>
#include <vector>
using namespace std;
int main(){
int C,N;
cin>>C>>N;
vector<int> weight(N,0);
vector<int> value(N,0);
vector<int> nums(N,0);
for(int i=0;i<N;i++){
cin>>weight[i];
}
for(int i=0;i<N;i++){
cin>>value[i];
}
for(int i=0;i<N;i++){
cin>>nums[i];
}
vector<int> dp(C+1,0);
dp[0] = 0;
for(int i=0;i<N;i++){
for(int j=C;j>=weight[i];j--){ //01背包，背包倒序遍历
for(int k=0;k<=nums[i]&&(j-k*weight[i])>=0;k++){
dp[j] = max(dp[j],dp[j-k*weight[i]]+k*value[i]);
}
}
}
cout<<dp[C];
return 0;
}