1
2
3
4

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

1
2
3

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

 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
33
34
35
36
37

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划(0-1背包问题)
    /// 1. 令 dp[i][j]: 表示最多i个0,j个1的最大子集数;
    /// 2. 递推关系: dp[i][j] = max(dp[i-z][j-o]+1)  (i=[z..=m], j=[o..=n]);
    /// 3. 初始条件: dp[0][0] = 0;
    /// 4. 终止条件: dp[m][n];
    pub fn find_max_form(strs: Vec<String>, m: i32, n: i32) -> i32 {
        fn str_01_count(str: &str) -> (usize, usize) {
            str.chars().fold((0, 0), |(mut z, mut o), c| {
                if c == '0' {
                    z += 1;
                } else {
                    o += 1;
                }
                (z, o)
            })
        }
        let (m, n) = (m as usize, n as usize);
        let mut dp = vec![vec![0_i32; n + 1]; m + 1];
        for str in &strs {
            let (z, o) = str_01_count(str);
            let (mut i, mut j) = (m, n);
            for i in (z..=m).rev() {
                for j in (o..=n).rev() {
                    dp[i][j] = dp[i][j].max(dp[i - z][j - o] + 1);
                }
            }
        }
        dp[m][n]
    }
}
// @lc code=end

struct Solution;