企石镇网站仿做,网站建设找好景科技,线上课程制作,网推软件目录
474. 一和零
518. 零钱兑换 II
377. 组合总和 Ⅳ 322. 零钱兑换 总结#xff1a; 474. 一和零 这道题和前面的思路一样#xff0c;就是需要将背包扩展到二维。
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vector 474. 一和零 这道题和前面的思路一样就是需要将背包扩展到二维。
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m1,vectorint(n1,0));for(auto s:strs){int oneNum0,zeroNum0;for(auto c:s){if(c0) zeroNum;else if(c1) oneNum;}for(int im;izeroNum;i--){for(int jn;joneNum;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, vectorint coins) {vectorint dp(amount1,0);dp[0]1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}return dp[amount];}
};
377. 组合总和 Ⅳ 这题和上题的区别在于这题是排列上题是组合。组合问题先遍历物品后遍历背包容积排列问题先遍历背包容积后遍历物品。进入循环里面思考一下就明白了怎么回事了。
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target1,0);dp[0]1;//遍历背包容积for(int j0;jtarget;j){//遍历物品for(int i0;inums.size();i){if(jnums[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(vectorint coins, int amount) {vectorint dp(amount1,INT_MAX);dp[0]0;for(int i0;icoins.size();i){for(int jcoins[i];jamount;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背包问题和完全背包问题的主要区别是元素是否可以无限制取。
在解决问题的方式上如果是求组合就先遍历物品再遍历背包容积如果是求排列就先遍历背包容积再遍历物品。
