474. 一和零（0,1背包）

题目链接

class Solution {
public:
    int findMaxForm(vector& strs, int m, int n) {
        // 初始化
        vector> dp(m + 1, vector(n + 1, 0));
        // 先获取每个元素有的0,1数目
        for (string str : strs) {
            int zeronum = 0;
            int oneNum = 0;
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            // 逆序
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    // dp[i][j]最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
                    dp[i][j] = max(dp[i][j], dp[i-zeroNum][j-oneNum] + 1);
                }
            }

        }

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

• 两个维度的01背包问题