474. Ones and Zeroes -M !!!!!! ~~~~~~~~

 Given an array, strs, with strings consisting of only 0s and 1s. Also two integers m and n.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

 

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0".

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

 

Constraints:

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] consists only of digits '0' and '1'.
• 1 <= m, n <= 100

A:

就是0/1 knapsack 问题。

本来一开始我觉得用3D array 做memorization . 太多了，不够。

就继续思考每次选最少0 或者 最少1 的。   结果不行（？？？？？？？？？为啥呢？）

最终，看了网上，每次增加一个 string.  并DP，

如果倒着计算，就可以直接利用之前的结果。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> V;
        for(auto str : strs){
            int c0 = 0, c1 = 0;
            for(auto ch : str){
                if(ch == '0'){
                    c0++;
                }else{
                    c1++;
                }
            }
            V.push_back(vector<int>{c0,c1});
        }
        // Now problem is to find longest subarray of V, S.t. V[i] to V[j] 
        // initially, we might need a 3D vector, V.size(), m+1, n+1 . But then it turns out if we update backword, then former values are not updated yet. So, we can use 2D
        vector<vector<int>> M(m+1,vector<int>(n+1,0));
        for(auto tmp : V){
            int c0 = tmp[0], c1 = tmp[1];
            for(int i = m; i>=0;i--){
                for(int j = n; j>=0; j--){
                    if(i-c0 >= 0 and j -c1 >=0 )
                        M[i][j] = max(M[i][j], 1 + M[i-c0][j-c1]);
                    else{
                        break;  // early break Just to speed up
                    }
                }
            }
        }
        return M[m][n];
    }
};