力扣题解（一和零）
给你一个二进制字符串数组 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];
}
};原文地址：https://blog.csdn.net/yyssas/article/details/140588888
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！