本文主要是介绍代码随想录训练营Day33:完全背包问题2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.322零钱兑换
与昨天的零钱兑换问题的区别主要不同点在于dp数组的含义，相同点都是属于组合问题。
1.dp数组的含义：dp[j]:代表容量为j时候的最少零钱个数
2.递推公式：dp[j] = min(dp[j],dp[j-coins[i]]+1);dp[j-coins[i]]+1 = dp[j - weight[i]]+value[i],所以还是属于一个变式。因为题目要求的是最小个数，所以得取min函数。
3.初始化：由于要取最小值，所以一开始初始化的时候不能设置为0，而是应该设置一个超过其对应范围的个数，可以是INT_32，也可以是10001因为题目中规定的范围是10000.但是dp[0] = 0,因为容量为0时放不进去零钱，所以为0.
4.因为这个题目里面需要的是最小的个数，这属于组合问题里面的一个叶子节点，所以遍历方式是先遍历种类再遍历容量。
class Solution {
public:int coinChange(vector<int>& coins, int amount) {sort(coins.begin(),coins.end());//先排序vector<int> dp(amount+1,10001);//dp[i]:价格为i的时候的最小的硬币个数dp[0] = 0;for(int i = 0;i<coins.size();i++){for(int j = coins[i];j<=amount;j++){dp[j] = min(dp[j],dp[j-coins[i]]+1);}}//if(amount == 0) return 0;if (dp[amount] == 10001) return -1;return dp[amount];}
};2.279完全平方数
1.dp数组的含义：dp[j]:代表容量为j时候的最少得完全平方数个数
2.递推公式：dp[j]= min(dp[j],dp[j-i*i]+1);dp[j-i*i]+1 = dp[j - weight[i]]+value[i],所以还是属于一个变式。因为题目要求的是最少个数，所以得取min函数。
3.初始化：由于要取最小值，所以一开始初始化的时候不能设置为0，而是应该设置一个超过其对应范围的个数，可以是INT_32，也可以是10001因为题目中规定的范围是10000.但是dp[0] = 0,因为容量为0时没有完全平方数，所以为0.
4.遍历顺序：因为这个题目里面需要的是最小的个数，这属于组合问题里面的一个叶子节点，所以遍历方式是先遍历种类再遍历容量。
整体下来和前面的类似。
class Solution {
public:int numSquares(int n) {vector<int> dp(n+1,10001);//dp[i]:容量为i的最少数量dp[0] = 0;for(int j = 1;j<=n;j++){for(int i = 1;i*i<=n;i++){if(j>=i*i)dp[j]= min(dp[j],dp[j-i*i]+1);}}return dp[n];}
};3.139单词拆分
1.dp数组的含义：dp[j]:容量为j的时候能否被拆分
2.递推公式：分三种情况：1.当dp[j-m](m为需要匹配的那个字典的长度)为false的时候直接返回false.2.当和这一段出现false的时候，结果为false。3.当dp[j-m]为true的同时这一段也能匹配，结果为true，然后break，代表这个长度可以匹配成功。
3.初始化：默认情况下为true，但是dp[0]为true.保证递推能够正常进行下去。
4.遍历顺序：这是属于完全背包下面的排列问题（因为要考虑顺序），所以是先遍历容量再遍历物品。
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.size();//这个应该是一个排列的问题，是需要考虑顺序的，所以应该先遍历容量vector<bool> dp(n+1,false);//dp[i]:长度为i的是否能够被找到dp[0] = true;//初始化for(int j = 1;j<=n;j++){//遍历背包容量for(auto& word:wordDict){//遍历物品int m = word.size();if(j >= m){if(dp[j-m] == false){//如果前面那个是false，那么直接返回falsedp[j] = false;continue;}bool ischeck = true;for(int k = 0;k<m;k++){//用来判断这一段是否能够匹配if(s[j-m+k]!=word[k]){ischeck = false;break;}}if(ischeck == true){//代表这一段匹配了，递推公式dp[j] = true;break;//找到了之后，后面的就不需要再找了}else{dp[j] = false;}}}}return dp[n];}
};这篇关于代码随想录训练营Day33:完全背包问题2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
