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];
    }
};

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注