AlgoPressAppearance
0474-一和零
https://leetcode.cn/problems/ones-and-zeroes
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] 仅由 '0' 和 '1' 组成
- 1 <= m, n <= 100
思路
动态规划 01背包问题
- dp[i,j,k] 表示从 0 到 i 中，装入输入的最大值，其中最多的0为j个，最多的1为k个
- 状态转移方程 dp[i,j,k] = max(dp[i-1,j,k],dp[i-1,j-0的数量,k-1的数量])
- 初始化
参考代码
csharp
public class Solution {
private int Count(string s, char c){
int count = 0;
for(int i = 0; i < s.Length; i++){
if(s[i] == c){
count++;
}
}
return count;
}
public int FindMaxForm(string[] strs, int m, int n) {
int[,,] dp = new int[strs.Length,m+1,n+1];
//初始化
for(int j=0; j<=m; j++){
for(int k=0; k<=n; k++){
if(Count(strs[0],'0') <=j && Count(strs[0],'1') <=k){
dp[0,j,k] = 1;
}
//Console.WriteLine("i={0},j={1},k={2},dp={3}",0,j,k,dp[0,j,k]);
}
}
//状态转移
for(int i=1; i<strs.Length; i++){
for(int j=0; j<=m; j++){
for(int k=0; k<=n; k++){
int zeroCount = Count(strs[i],'0');
int oneCount = Count(strs[i],'1');
if(j>=zeroCount && k>=oneCount){
dp[i,j,k] = Math.Max(dp[i-1,j,k],dp[i-1,j-zeroCount,k-oneCount]+1);
}
else{
dp[i,j,k] = dp[i-1,j,k];
}
//Console.WriteLine("i={0},j={1},k={2},dp={3}",i,j,k,dp[i,j,k]);
}
}
}
//返回结果
return dp[strs.Length-1,m,n];
}
}
复习：滚动数组写法
注意状态转移方程是 max(dp[j,k],dp[j-zeros,k-ones]+1) , 长度延长1
csharp
public class Solution {
private int count(string str, char c){
int sum = 0;
for(int i=0; i<str.Length; i++){
if(str[i] == c){
sum++;
}
}
return sum;
}
public int FindMaxForm(string[] strs, int m, int n) {
// 动态规划，01背包问题
// 定义 dp[j,k] 表示包含 j个0,k个1的子集的最大长度
int[,] dp = new int[m+1,n+1];
//统计0和1的个数
int strLength = strs.Length;
int[] zeros = new int[strLength];
int[] ones = new int[strLength];
for(int i=0; i<strs.Length; i++){
zeros[i] = count(strs[i],'0');
ones[i] = strs[i].Length - zeros[i];
}
for(int i=0; i<strs.Length; i++){ //循环物品
for(int j=m; j>=0; j--){ // 0 从后往前遍历
for(int k=n; k>=0; k--){ // 1
if(j>=zeros[i] && k>=ones[i]){
dp[j,k] = Math.Max(dp[j,k], dp[j-zeros[i],k-ones[i]] + 1);
}
}
}
}
return dp[m,n];
}
}
复习：20220630
注意背包的限制是二维的，当1和0都满足的时候，进行状态转移
csharp
public class Solution {
private int GetCount(string str, char c){
int count = 0;
for(int i=0; i<str.Length; i++){
if(c == str[i]){
count++;
}
}
return count;
}
public int FindMaxForm(string[] strs, int m, int n) {
// 01 背包问题，从n个数中选择几个数，背包容量是 m和n
// dp[j,k] 表示装入背包容量j,k的最大数字个数
int[,] dp = new int[m+1,n+1];
for(int i=0; i<strs.Length; i++){ //遍历物品
for(int j=m; j>=0; j--){ //遍历背包
for(int k=n; k>=0; k--){
int zeroCount = GetCount(strs[i],'0');
int oneCount = GetCount(strs[i],'1');
if(j >= zeroCount && k>= oneCount){
dp[j,k] = Math.Max(dp[j,k], dp[j-zeroCount,k-oneCount]+1);
}
}
}
}
return dp[m,n];
}
}