程式語言 - LeetCode - C++ - 474. Ones and Zeroes


題目：


方法： 

處理 "10"
      0 1 2 3
    +---------
0   | 0 0 0 0
1   | 0 1 1 1
2   | 0 1 1 1
3   | 0 1 1 1
4   | 0 1 1 1
5   | 0 1 1 1


處理 "0001"
      0 1 2 3
    +---------
0   | 0 0 0 0
1   | 0 1 1 1
2   | 0 1 1 1
3   | 0 1 1 1
4   | 0 1 2 2
5   | 0 1 2 2


處理 "111001"
      0 1 2 3
    +---------
0   | 0 0 0 0
1   | 0 1 1 1
2   | 0 1 1 1
3   | 0 1 1 1
4   | 0 1 2 2
5   | 0 1 2 2


處理 "1"
      0 1 2 3
    +---------
0   | 0 1 1 1
1   | 0 1 2 2
2   | 0 1 2 2
3   | 0 1 2 2
4   | 0 1 2 3
5   | 0 1 2 3


處理 "0"
      0 1 2 3
    +---------
0   | 0 1 1 1
1   | 1 2 2 2
2   | 1 2 3 3
3   | 1 2 3 3
4   | 1 2 3 3
5   | 1 2 3 4

解答： 

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (string s : strs) {
            int c0 = 0;
            int c1 = 0;

            for (char c : s) {
                if (c == '0') {
                    c0 += 1;
                }
                else {
                    c1 += 1;
                }
            }

            for (int i = m; i >= c0; --i) {
                for (int j = n; j >= c1; --j) {
                    dp[i][j] = max(dp[i][j], dp[i - c0][j - c1] + 1);
                }
            }
        }

        return dp[m][n];
    }
};