一和零

474. 一和零 - 力扣（LeetCode）

其實遇到這種還好說，我寧愿遇見這種，也不想遇見那些奇奇怪怪遞推公式的題目。

這里其實相當背包要滿足兩個條件，所以我們可以將dp開成二維的，之后的操作，其實就是和普通01背包差不多啦~注意這里是要求的子串個數，所以我們遞推公式最后是+1。

AC：

//dp[i][m][n]表示前i個的元素中，能滿足最多m個0，n個1的子集最多個數
int findMaxForm(vector<string>& strs, int m, int n)
{vector<vector<int>>dp(m+1,vector<int>(n+1));for(int i=0;i<strs.size();i++){int a0=0,a1=0;for(auto it:strs[i]){if(it=='1')    a1++;else a0++;}for(int j=m;j>=a0;j--) {for(int k=n;k>=a1;k--){dp[j][k]=max(dp[j][k],dp[j-a0][k-a1]+1);}}}return dp[m][n];
}