力扣题解（一和零）

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

思路：

本题可以看成有两个限制条件的01背包问题，因此可以规定dp[i][j][k]表示前i个子串，0的个数不大于j，1的个数不大于k的情况下的最长长度。则dp[i][j][k]=max（dp[i-1][j][k] ,dp[i-1][j-z[i][k-o[i]]+1）,其中z[i]表示第i个子序列中0的个数，o[i]表示第i个子序列中1的个数。

初始化：

j，k均为0的时候，无论i取什么值都存在且仅存在一个不取的情况下让j，k均为0，因此dp[i][0][0]=1.

优化：可以把dp从三维换成二维，因为此处dp[i][][]只和dp[i-1][][]有关，因此可以将第一维去掉，但需要注意此时必须让j，k从大到小变化，这样才能保证dp[j][k]是上一个i所对应的dp。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
      int row=strs.size();
      vector<pair<int,int>>strnum(row+1,{0,0});
            vector<vector<int>>dp(m+1,vector<int>(n+1,0));

      for(int i=0;i<row;i++)
      {
         for(auto e:strs[i])
         {
            if(e=='0')
            {
                strnum[i+1].first++;
            }
            else
            strnum[i+1].second++;

         }
          for(int j=m;j>=strnum[i+1].first;j--)
        {
            for(int k=n;k>=strnum[i+1].second;k--)
            {
           
        
             dp[j][k]=max(dp[j][k],dp[j-strnum[i+1].first][k-strnum[i+1].second]+ 1);              
            }
        }
      }

       
      

      return dp[m][n];
    }
};