【leetcode】474. Ones and Zeroes

题目如下：

解题思路：二维背包问题。记dp[i][j][k]为前i个元素中使用了j个0，k个1可以获得的最大值。对于Array[i]来说，有选和不选两种操作，如果不选，那么dp[i][j][k] = dp[i-1][j][k]，如果选那么则有dp[i][j][k] = dp[i-1][j-i0][k-i1] (i0和i1分别为Array[i]中0和1的数量)。这种解法的时间复杂度是O(n^3)，用python会超时，用C++则能通过。

代码如下：

python

### TEL, C++ Accpeted

class Solution(object):
    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        res = 0
        dp = [[[0 for x in range(n + 1)] for x in range(m + 1)] for x in strs]
        c1 = strs[0].count('1')
        c0 = strs[0].count('0')
        if c0 <= m and c1 <= n:
            dp[0][c0][c1] = 1
            res = max(res, dp[0][c0][c1])
        count = 0
        for i in range(1,len(strs)):
            for j in range(m + 1):
                for k in range(n + 1):
                    count += 1
                    dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][k])
                    c1 = strs[i].count('1')
                    c0 = strs[i].count('0')
                    if j - c0 >= 0 and k - c1 >= 0:
                        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - c0][k - c1] + 1)
                    res = max(res,dp[i][j][k])
        return res

C++

#include <vector>
#include <map>
#include <string>
using namespace std;

class Solution {
public:
    int getCount(string str,char val){
        int count = 0;
        for(int i = 0;i<str.size();i++){
            if (val == str[i]){
                count += 1;
            }
        }
        return count;
    }
    #define MAX(a,b) ((a) < (b) ? (b) : (a))
    int findMaxForm(vector<string>& strs, int m, int n) {
        //memset(dp,0,1000*101*101);
        int dp[600][101][101] = {0};
        int res = 0;
        int c1 = getCount(strs[0],'1');
        int c0 = getCount(strs[0],'0');
        if (c0 <= m && c1 <= n){
            dp[0][c0][c1] = 1;
            res = MAX(res, dp[0][c0][c1]);
        }
        for(int i = 1;i<strs.size();i++){
            for(int j = 0;j<=m;j++){
                for(int k = 0;k<=n;k++){
                    dp[i][j][k] = MAX(dp[i][j][k],dp[i-1][j][k]);
                    c1 = getCount(strs[i],'1');
                    c0 = getCount(strs[i],'0');
                    if (j - c0 >= 0 && k - c1 >= 0){
                        dp[i][j][k] = MAX(dp[i][j][k], dp[i - 1][j - c0][k - c1] + 1);
                    }
                    res = MAX(res,dp[i][j][k]);
                }
            }
        }
        return res;
    }
};