474. Ones and Zeroes

https://leetcode.com/problems/ones-and-zeroes/

solution:
这是个2维01背包问题 (two-D 0-1 Knapsack Problem). 所以不再啰嗦了， 如果第一次见到此类问题，就google "Knapsack Problem".

代码：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        //two-dimentional 0-1 knapsack problem.
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(auto s:strs){
            int count1 = 0, count2 = 0; // count1 for '0' and count2 for '1';
            for(auto c:s){
                if(c=='0') ++count1;
                else ++count2;
            }
            for(int i=m; i>count1-1; --i){
                for(int j=n; j>count2-1; --j){
                    dp[i][j] = max(dp[i][j], dp[i-count1][j-count2] + 1);
                }
            }
        }
        return dp[m][n];
    }
};