LeetCode #474：Ones And Zeroes(一和零)

题目描述

本题依然是 01 背包问题，不过背包有两个维度（m 和 n），是一个二维 01 背包。故 dp 数组要开二维、需要三重循环得出结果。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // dp[i][j]：最多有i个0和j个1的strs的最大子集长度为dp[i][j]

        for(string str: strs) { // 遍历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] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); // 放当前物品和不放当前物品的长度取最大值
                }
            }
        }

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