Leetcode 474. Ones and Zeroes (python+cpp)

题目

解法1：动态规划

这也是一个0，1背包问题，但是有两个背包，分别是0的数量和1的数量。所以相应最直观的解法如下：

• 定义一个3维的dp数组，长度分别为L+1，m+1，n+1，l，m，n分别为string的数量，0的数量和1的数量
• dp[L][i][j]代表当包含前L个string，并且有i个0，j个1的时候，能形成的string最大数量是多少
• 更普通背包问题一样，当前的结果应该等于取当前的string和不取当前string的最大值，状态转移方程为：

// zeros和ones代表当前正在遍历的string包含的0的个数或者1的个数
if (j>=zeros && k>=ones)dp[i][j][k] = max(dp[i-1][j][k], 1 + dp[i-1][j-zeros][k-ones] );
elsedp[i][j][k] = dp[i-1][j][k];

由于python好像没有表示3维数组的方法，所以这边是用C++来写的，代码如下：

typedef vector<int> v1d;
typedef vector<v1d> v2d;
typedef vector<v2d> v3d;
class Solution {
    
public:int findMaxForm(vector<string>& strs, int m, int n) {
    int l = strs.size();v3d dp(l+1, v2d(m+1, v1d(n+1, 0))); //dp[l+1][m+1][n+1]for(int i=1;i<=l;i++){
    string s = strs[i-1];int ones = count(s.begin(), s.end(), '1');int zeros = s.size()-ones;for (int j=0;j<=m;j++){
    for (int k=0;k<=n;k++){
    if (j>=zeros && k>=ones)dp[i][j][k] = max(dp[i-1][j][k], 1 + dp[i-1][j-zeros][k-ones] );elsedp[i][j][k] = dp[i-1][j][k];}//k}//j}//ireturn dp[l][m][n];}
};

但是呢，这种方法应该不是大家所常见到的方法，对于这道题最常见的解法应该是进行状态压缩之后的解法，用2维dp来做。
python代码如下：

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:dp = [[0]*(n+1) for _ in range(m+1)]for s in strs:ones, zeros = s.count('1'), s.count('0')for i in range(m,zeros-1,-1):for j in range(n,ones-1,-1):dp[i][j] = max(1+dp[i-zeros][j-ones],dp[i][j])return dp[-1][-1]

C++代码如下：

class Solution {
    
public:int findMaxForm(vector<string>& strs, int m, int n) {
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));for (auto s:strs){
    int ones = count(s.begin(), s.end(), '1');int zeros = s.size()-ones;for (int i=m;i>=zeros;i--){
    for (int j=n;j>=ones;j--){
    dp[i][j] = max(dp[i][j],1+dp[i-zeros][j-ones]);}}}return dp[m][n];}
};

这边可能会有人问为什么二维的必须降序遍历，而不是像正常的正向遍历。这就牵涉到背包问题里建dp表是采用top down还是bottom up，在进行普通的动态规划而不进行状态压缩的时候，一般就是采用top down，而在进行状态压缩的时候，会碰到所谓的Overlapping Subproblems in knapsack problem.关于这个问题的详细解释，建议看这个网址，里面的讨论很清晰https://leetcode.com/problems/ones-and-zeroes/discuss/95814。

解法2：recursion + memorization

就像我之前一直说的，可以用动态规划解决的问题，一般都是可以用recursion+memorization解决的。但是由于这边重点在动态规划，所以我就直接上代码
python代码如下：

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:def dfs(idx,remain0,remain1):if idx>=len(strs):return 0if (idx,remain0,remain1) in memo:return memo[(idx,remain0,remain1)]num0,num1 = strs[idx].count('0'),strs[idx].count('1')taken = 0if remain0-num0>=0 and remain1-num1>=0:taken = dfs(idx+1,remain0-num0,remain1-num1,)+1not_taken = dfs(idx+1,remain0,remain1)memo[(idx,remain0,remain1)]  = max(taken,not_taken)return memo[(idx,remain0,remain1)] memo = {
    }return dfs(0,m,n)