网站流程图软件关键词制作软件
目录
474. 一和零
518. 零钱兑换 II
377. 组合总和 Ⅳ
322. 零钱兑换
总结：
474. 一和零
这道题和前面的思路一样，就是需要将背包扩展到二维。
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(auto s:strs){int oneNum=0,zeroNum=0;for(auto c:s){if(c=='0') zeroNum++;else if(c=='1') oneNum++;}for(int i=m;i>=zeroNum;i--){for(int j=n;j>=oneNum;j--){dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);}}}return dp[m][n];}
};518. 零钱兑换 II
每个硬币可以无限制取，完全背包问题。先确定dp[i]表示的含义，i表示背包容量，dp[j]表示该容量有多少种方法。再确定递推公式，dp[j]+=dp[j-coins[i]];。最后确定遍历顺序，因为每个硬币都可以无限制取，所以j的遍历顺序应该为正序。
注意：在01背包中为了防止元素重复取，采用倒序
class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount+1,0);dp[0]=1;for(int i=0;i<coins.size();i++){for(int j=coins[i];j<=amount;j++){dp[j]+=dp[j-coins[i]];}}return dp[amount];}
};
377. 组合总和 Ⅳ
这题和上题的区别在于这题是排列，上题是组合。组合问题先遍历物品后遍历背包容积，排列问题先遍历背包容积后遍历物品。进入循环里面思考一下就明白了怎么回事了。
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target+1,0);dp[0]=1;//遍历背包容积for(int j=0;j<=target;j++){//遍历物品for(int i=0;i<nums.size();i++){if(j<nums[i] || dp[j]>INT_MAX-dp[j-nums[i]]) continue;dp[j]+=dp[j-nums[i]];}}return dp[target];}
};322. 零钱兑换
这题的不同之处在于求最小硬币个数，初始化的时候注意初始化为最大值。
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1,INT_MAX);dp[0]=0;for(int i=0;i<coins.size();i++){for(int j=coins[i];j<=amount;j++){//如果dp[j-coins[i]]==INT_MAX，将超出int的范围if(dp[j-coins[i]]!=INT_MAX)dp[j]=min(dp[j],dp[j-coins[i]]+1);}}if(dp[amount]==INT_MAX) return -1;return dp[amount];}
};总结：
01背包问题和完全背包问题的主要区别是元素是否可以无限制取。
在解决问题的方式上，如果是求组合就先遍历物品再遍历背包容积，如果是求排列就先遍历背包容积再遍历物品。