代码随想录day38 动态规划6

题目：322.零钱兑换 279.完全平方数 139.单词拆分多重背包背包总结

需要重做：322，139

322. 零钱兑换

思路：零钱，可取多次-》完全背包。

注意：

五部：

1.dp[j]:价值为j的时候，最少需要几个coin

2.dp[j]=min(dp[j],dp[j-coins[i]]+1)

3.由递推式可知，0一定是0，其余的必须是INT——MAX或者根据题目要求的大的数，才能保证后面的不被0覆盖，而是由推出来的赋值的

4.先物品后bagsize

代码：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int n=coins.size();vector<int>dp(amount+1,10001);dp[0]=0;//初始化dp[0]为0即可。for(int i=0;i<n;i++){for(int j=0;j<=amount;j++){if(j>=coins[i])dp[j]=min(dp[j],dp[j-coins[i]]+1);}}if(dp[amount]==10001&&amount!=0)return -1;else return dp[amount]; }
};

279.完全平方数

思路：跟上题的思路类似，但是初始化的时候有点不一样。以下给出两种解法

注意：初始化需要推导

五部：

1.dp[j]:总价值为j，我最少要多少个数

2.dp[j]=min(dp[j],dp[j-val[i]]+1);(代码1需要多一条特殊情况)

3.代码1 2给出两种

4.先val再bagsize或者先bagsize后val都行

代码1：初始化，dp[0]不初始化，单独列出

class Solution {
public:int numSquares(int n) {int val[102]={0};for(int i=0;i<=101;i++){val[i]=i*i;}vector<int>dp(n+1,10001);dp[1]=1;for(int i=1;val[i]<=n;i++){for(int j=val[i];j<=n;j++){dp[j]=min(dp[j],dp[j-val[i]]+1);if(j==val[i])dp[j]=min(dp[j],1);}}return dp[n];}
};

代码2：初始化dp[0]=0,无意义，但是写法能统一

class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i * i <= n; i++) { // 遍历物品for (int j = i * i; j <= n; j++) { // 遍历背包dp[j] = min(dp[j - i * i] + 1, dp[j]);}}return dp[n];}
};

139.单词拆分

思路：可以想到回溯，但是回溯对于字符串的处理复杂，且不充分剪枝会超时，考虑dp。

将字符串里不同的单词看作物品，将整个字符串看作bagsize

注意：

五部：

1.dp[j]:该字符串长度为j的时候是否可以由字典的词组成

2.记 i<j ，如果i是true，且i到j在字典里，则j为true

3.初始化：dp[0]=true,其余为false

4.一定要先bagsize后物品，因为有要求顺序，是排列

代码：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int bagsize=s.size();int n=wordDict.size();vector<int>dp(bagsize+1,0);dp[0]=1;unordered_set<string>wordSet(wordDict.begin(),wordDict.end());for(int j=1;j<=bagsize;j++){//先遍历背包容量for(int i=0;i<j;i++){//再遍历背包的所有物品string word=s.substr(i,j-i);if(wordSet.find(word)!=wordSet.end()&&dp[i]){dp[j]=1;}}}return dp[bagsize];}
};

关于多重背包，你该了解这些！

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

所以多重背包本质上是01背包

#include<iostream>
#include<vector>
using namespace std;
int main(){int c,n;cin>>c>>n;vector<int>weight(n,0);vector<int>val(n,0);vector<int>num(n,0);for(int i=0;i<n;i++)cin>>weight[i];for(int i=0;i<n;i++)cin>>val[i];for(int i=0;i<n;i++)cin>>num[i];vector<int>dp(c+1,0);for(int i=0;i<n;i++){//遍历物品for(int j=c;j>=weight[i];j--){//j为背包容量for(int k=1;k<=num[i]&&j>=k*weight[i];k++){//遍历个数dp[j]=max(dp[j],dp[j-k*weight[i]]+k*val[i]);}}}cout<<dp[c];
}