Competitive_Programming/LeetCode/Full_List/474.cpp at master · Ravi-Maurya/Competitive_Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
public:
    int dp[605][105][105];
    void convert(vector<string>& strs, vector<int>& ones, vector<int>& zeroes){
        for(int i=0; i<strs.size(); i++){
            string st = strs[i];
            for(int j=0; j<st.size(); j++){
                int x = st[j]-'0';
                if(x==1)
                    ones[i]++;
                else
                    zeroes[i]++;
            }
        }
        return;
    }

    int recursion(vector<int>& ones, vector<int>& zeroes, int idx, int n, int m){
        if(idx>=zeroes.size()){
            return 0;
        }
        if(dp[idx][n][m]!=-1)
            return dp[idx][n][m];
        if(ones[idx]<=n && zeroes[idx]<=m){
            return dp[idx][n][m] = max(recursion(ones,zeroes,idx+1,n,m), 1 + recursion(ones,zeroes,idx+1,n-ones[idx],m-zeroes[idx]));
        }
        return dp[idx][n][m] = recursion(ones,zeroes,idx+1,n,m);
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        int size = strs.size();
        vector<int> ones(size,0), zeroes(size,0);
        convert(strs,ones,zeroes);
        memset(dp,-1,sizeof(dp));
        return recursion(ones,zeroes,0,n,m);
    }
};


class Solution {
public:
    int dp[605][105][105];
    void convert(vector<string>& strs, vector<int>& ones, vector<int>& zeroes){
        for(int i=0; i<strs.size(); i++){
            string st = strs[i];
            for(int j=0; j<st.size(); j++){
                int x = st[j]-'0';
                if(x==1)
                    ones[i]++;
                else
                    zeroes[i]++;
            }
        }
        return;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        int size = strs.size();
        vector<int> ones(size,0), zeroes(size,0);
        convert(strs,ones,zeroes);
        memset(dp,0,sizeof(dp));
        for(int i=0; i<=n; i++)
            for(int j=0; j<=m; j++){
                if(ones[0]<=i && zeroes[0]<=j)
                    dp[0][i][j] = 1;
                else
                    dp[0][i][j] = 0;
            }
        for(int i=1; i<size; i++){
            for(int j=0; j<=n; j++){
                for(int k=0; k<=m; k++){
                    if(ones[i]<=j && zeroes[i]<=k){
                        dp[i][j][k] = max(dp[i-1][j][k], 1 + dp[i-1][j-ones[i]][k-zeroes[i]]);
                    }
                    else{
                        dp[i][j][k] = dp[i-1][j][k];
                    }
                }
            }
        }
        return dp[size-1][n][m];
    }
};