474. 一和零

474. 一和零
     中等
     817
     相关企业
     给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：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 。
示例 2：

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

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100

// 这个题目使用回溯算法肯定可以，列举出来所有的子集以后，找到符合条件的子集，然后就可以了，但是估计会超时
// 如何转换一下用动态规划进行解决呢？
// 其实就是背包问题变得复杂一点了，一维的背包变成2维的了，都是满满的套路
// 1、确定dp数组的含义
// dp[i][m][n] 表示从0到i的字串包含m个0和n个1的子集的长度是多少
// 2、确定递推公式
// 根据题意，对于当前第i个字串，有两种方式进行处理
// 1)如果不选当前的字串，那么dp[i][m][n] = dp[i - 1][m][n];
// 2)如果选当前的字串，那么dp[i][m][n] = dp[i - 1][m-strs[i]的0的个数][n-strs[i]的1个个数] + 1
// 因此根据题意，dp[i][m][n] = max {dp[i-1][m][n], dp[i-1][m-strs[i]的0的个数][n-strs[i]的1的个数] + 1}
// 3、初始化
// 如果i=0 那么 m和n大于第一个字串的dp位置就要初始化为1
// 如果m=0 或者 n=0， 那么dp全部为0;
// 4 计算方向
// 按照先字串，然后m，然后n的方式进行三层循环嵌套计算
// 5、获取结果
// 结果就位于dp[strSize - 1][m][n]位置
// 6、输入例子验证
// 三维数组有点麻烦，第一个case进去肯定是可以的

struct nums {
    int ling;
    int yi;
};

int max1(int a, int b)
{
    return a>b?a:b;
}
int findMaxForm(char ** strs, int strsSize, int m, int n){
    // 对strs进行初始化，统计其中的每个字串0和1的个数
    // 申请二维数组，然后进行统计
    struct nums* arr = (struct nums*)malloc(sizeof(struct nums) * strsSize);

    int i,j,k;
    int len;
    int YI;
    for (i = 0; i < strsSize; i++) {
        len = strlen(strs[i]);
        YI = 0;
        for (j = 0; j < len; j++) {
            if (strs[i][j] == '1')
            YI++;
        }
        arr[i].yi = YI;
        arr[i].ling = len - YI;
    }


    // 申请dp数组
    int*** dp = (int***)malloc(sizeof(int**) * (strsSize + 1));
    for (i = 0; i < strsSize + 1; i++) {
        dp[i] = (int**)malloc(sizeof(int*) * (m + 1));
        for (j = 0; j < m + 1; j++) {
            dp[i][j] = (int*)malloc(sizeof(int) * (n + 1));
            memset(dp[i][j], 0x00, sizeof(int) * (n + 1));
        }
    }
    // 对dp数组进行初始化
    for (i = arr[0].ling; i < m + 1; i++) {
        for (j = arr[0].yi; j < n + 1; j++) {
            dp[0][i][j] = 1;
        }
    }
    // 按照规定的情况进行循环计算
    for (i = 0; i < m + 1; i++) {
        for (j = 0; j < n + 1; j++) {
            for (k = 1; k < strsSize; k++) {
                if (i >= arr[k].ling && j >= arr[k].yi) {
                    dp[k][i][j] = max1(dp[k - 1][i][j], dp[k - 1][i - arr[k].ling][j-arr[k].yi] + 1);
                } else {
                    dp[k][i][j] = dp[k - 1][i][j];
                }
                
            }
        }
    }

    int ans = dp[strsSize - 1][m][n];
// 释放dp数组
    for (i = 0; i < strsSize + 1; i++) {
        for (j = 0; j < m + 1; j++) {
            free(dp[i][j]);
            dp[i][j] = NULL;
        }
        free(dp[i]);
        dp[i] = NULL;
    }
    free(dp);
    dp = NULL;


    return ans; 



}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97