LeetCode474 一和零

发表于 | 分类于 |
字数统计: 491 | 阅读时长 ≈ 2

链接：https://leetcode-cn.com/problems/ones-and-zeroes/description/

题面

给定 m 个数字 0 和 n 个数字 1，以及一些由 0-1 构成的字符串，求利用这些数字最多可以构成多少个给定的字符串，字符串只可以构成一次。

解法

这是一饿多维费用的0-1背包问题
有两个背包大小，0的数量和1的数量
一开始的写法是令dp[i][j]表示i个0, j个1的最大子集的元素个数
这种写法下需要将原始dp数值初始化为负值
每次更新dp值的时候都进行判断 找出要的结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    pair<int, int> getCount(string& s) {
        int cnt1 = 0, cnt2 = 0;
        for(char c: s) {
            if (c == '0') {
                cnt1++;
            }
            else {
                cnt2++;
            }
        }
        return {cnt1, cnt2};
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, -strs.size()));
        dp[0][0] = 0;
        int ans = 0;
        // dp[i][j] 表示i个0, j个1的最大子集的元素个数
        for(auto s: strs) {
            auto ret = getCount(s);
            int rf = ret.first, rs = ret.second;
            for (int i = m; i >= rf; i--) {
                for (int j = n; j >= rs; j--) {
                        dp[i][j] = max(dp[i][j], dp[i - rf][j - rs] + 1);
                        ans = max(ans, dp[i][j]);
                }
            }
        }
        return ans;
    }
};

那么还有一种比较普遍性的做法是令dp[i][j]表示不超过i个0, j个1的最大子集的元素个数
这样就初始化为0，并且直接更新就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[0][0] = 0;
        // dp[i][j] 表示不超过i个0, j个1的最大子集的元素个数
        for(auto s: strs) {
            auto ret = getCount(s);
            int rf = ret.first, rs = ret.second;
            for (int i = m; i >= rf; i--) {
                for (int j = n; j >= rs; j--) {
                        dp[i][j] = max(dp[i][j], dp[i - rf][j - rs] + 1);
                }
            }
        }
        return dp[m][n];
    }