代码随想录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];
}

背包问题总结篇！摘自代码随想录

五部：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

背包递推公式

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

• 动态规划：416.分割等和子集(opens new window)
• 动态规划：1049.最后一块石头的重量 II(opens new window)

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

• 动态规划：494.目标和(opens new window)
• 动态规划：518. 零钱兑换 II(opens new window)
• 动态规划：377.组合总和Ⅳ(opens new window)
• 动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：

• 动态规划：474.一和零(opens new window)

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

• 动态规划：322.零钱兑换(opens new window)
• 动态规划：279.完全平方数(opens new window)

#遍历顺序

#01背包

在动态规划：关于01背包问题，你该了解这些！ (opens new window)中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

和动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中，我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。

一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的，大家需要注意！

#完全背包

说完01背包，再看看完全背包。

在动态规划：关于完全背包，你该了解这些！ (opens new window)中，讲解了纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

相关题目如下：

• 求组合数：动态规划：518.零钱兑换II(opens new window)
• 求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

如果求最小数，那么两层for循环的先后顺序就无所谓了，相关题目如下：

• 求最小数：动态规划：322. 零钱兑换 (opens new window)、动态规划：279.完全平方数(opens new window)

对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解了。

#总结

这篇背包问题总结篇是对背包问题的高度概括，讲最关键的两部：递推公式和遍历顺序，结合力扣上的题目全都抽象出来了。

而且每一个点，我都给出了对应的力扣题目。

最后如果你想了解多重背包，可以看这篇动态规划：关于多重背包，你该了解这些！ (opens new window)，力扣上还没有多重背包的题目，也不是面试考察的重点。