一和零 （leetcode 474

leetcode系列

文章目录

• 一、核心操作
• 二、外层配合操作
• 三、核心模式代码
• 总结

---

本题是一个01背包问题，只是背包是一个二维数组的背包，分别为0的个数不能超过m，1的个数不能超过n，而物品就是题目中的字符串，其容量为0和1的个数，而价值就是1，本题要在给定的背包容量中，使得价值尽可能的高，也就是尽可能多的拿字符串

一、核心操作

1. dp[i][j]代表0的个数不超过i，1的个数不超过j的情况下，字符串的最大数量
2. 递推公式：当本次拿取的字符串不超过背包容量时，可以比较是不拿这个字符串的的总共数量多，还是拿这个字符串的总共数量多，即比较dp[i][j]和dp[i-zero][j-one]+1；如果超过了背包容量那就不用比较了，直接就不用动了（因为是滚动数组，每一次都直接在上一层的基础上更新）
3. 初始化：由于个数是从0开始的，都初始化为0就可以
4. 遍历顺序：两个都是从后往前，只有这样才不会重复放入字符串

提示：小白个人理解，如有错误敬请谅解！

二、外层配合操作

1. 每次都从字符串数组中拿取一个，统计这个字符串0和1的数量，然后根据这个来更新本层的数据

三、核心模式代码

代码如下：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(string str : strs){int zero=0;int one=0;for(auto & s :str){if(s=='0')zero++;else one++;}for(int i=m;i>=zero;i--){for(int j=n;j>=one;j--){dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1);}}}return dp[m][n];}
};

---

总结

1. 其实按照标准的01背包来看，此题应该用一个三维数组，但是三维数组对资源占用太大了，代码如下：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<vector<int>>> dp (strs.size(),vector<vector<int>>(m+1,vector<int>(n+1,0)));vector<int> zero;vector<int> one;for(string str : strs){int zeroNum=0;int oneNum=0;for(char s : str){if(s=='0')zeroNum++;else oneNum++;}one.push_back(oneNum);zero.push_back(zeroNum);}if(zero[0]<=m && one[0]<=n){for(int j=zero[0];j<=m;j++){for(int k=one[0];k<=n;k++){dp[0][j][k]=1;}}}for(int i=1;i<strs.size();i++){for(int j=0;j<=m;j++){for(int k=0;k<=n;k++){if(j<zero[i] || k<one[i])dp[i][j][k]=dp[i-1][j][k];else dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zero[i]][k-one[i]]+1);}}}return dp[strs.size()-1][m][n];}
};