leetcode：474. Ones and Zeroes 解题思路以及01背包问题浅析

刷题刷到这里，先说题目：给定一组字符串，其中每个字符串中只包含‘0’和‘1’，给定你m个0 和n 个1，求最多能排出多少个字符串。
乍一看这题，貌似在哪里见过，貌似又没见过，哎，一排脑袋，01背包，只不过变成了二维的。在此，我们就先复习一下一维的01背包问题，以备后用~~~
N个物品，每个价值value[i], 需要占用空间need[i],给定一个登山包(不知道哪年买的。。。），容量为M，求用该登山包装这N个物品，最大价值能装多少。
不多说，直接dp，递推公式为dp[i][j] = max(dp[i-1][j], dp[i-1][j-need[i]]+value[i])，第一版代码如下：

for( i = 1; i <=N ; ++i)
{
    for( j = 0; j <= M; j++)
    {
        if( j >= need[i] )
            best[i][j] = max( best[i-1][j], best[i-1][j - need[i]] + value[i]);
        else
            best[i][j] = best[i-1][j];
    }
}

接下来考虑优化问题，这种递推能不能将空间复杂度降低至O(M)呢，答案是肯定的，请看下面的代码：

for( i = 1; i <=N ; ++i)
{
    for( j = M; j >= 0; --j)
    {
        if( j >= need[i] )
            best[j] = max( best[j], best[j - need[i]] + value[i]);
    }
}

为什么对j要进行倒序遍历呢？这是因为在计算本轮第i个物品的时候，需要用到上一轮i-1个物品时的状态，而如果正向递增遍历，则会更新掉前面的数据，故采用倒叙遍历啦~~
有了如上的思路，变换为leetcode的题目，大家就不难找出解决思路了吧，先求出每个字符串对应需要的0和1的个数，相当于01背包中的need[i]，给定的m和n相当于01背包中的背包容量M，代码如下：

int findMaxForm(vector<string>& strs, int m, int n){
    int len = strs.size(), i, j, M, N;
    if(len == 0||(m==0&&n==0)) return 0;
    vector<vector<int>> dp(len, vector<int>(2, 0));
    for(i = 0; i < len; i++)
        for(j = 0; j < strs[i].length(); j++){
            if(strs[i][j]=='0') dp[i][0]+=1;
            else dp[i][1]+=1;
        }
    vector<vector<int>> res(m+1, vector<int>(n+1, 0));
    for(i = 0; i < len; i++){
        for(M=m; M>=0;M--)
            for(N=n; N>=0;N--)
                if(M>=dp[i][0]&&N>=dp[i][1]){
                    res[M][N]= max(res[M][N], res[M-dp[i][0]][N-dp[i][1]]+1);
                }
    }
    return res[m][n];
}

谢谢大家观看~~~