代码随想录笔记_动态规划_474一和零

代码随想录二刷笔记记录

LC474.一和零

---

题目

01背包

给你一个二进制字符串数组 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

---

思路分析

思路：
strs数组中的元素看作物品，m和n相当于是一个二维背包

选取物品时，不仅要考虑 m(1的数量) 还要考虑 n (0的数量)

动态规划五部曲

1.确定dp数组及其下标的含义

dp[i][j]: 由 i 个 0 和 j 个 1 组成的字符串数组strs最大子集的大小
1

2.确定递推公式

由题可知，子集的 0 和 1 的数量 (zeroNum,oneNum) 不能超过限定的数量 m,n

回顾 01背包 递推公式

//二维
dp[i][j] = Max(dp[i][j],dp[i][j - weight[i]] + value[i])
//一维
dp[j] = Max(dp[j],dp[j - weight[i]] + value[i])
1
2
3
4

本题的当前状态，需要从前一个状态推导而来
dp[i][j] 需要由前一个 strs 数组中的字符串 s 所推导而来。
推导时需要判断 s 的 zeroNum 和 oneNum 是否超过了限制的m和n
因此：

i + zeroNum <= m , j + oneNum <= n
1

推导过程取最大值,即最大子集，则有递推公式

dp[i][j] = Max(dp[i][j],dp[i - zeroNum][j - oneNum] + 1)
1

可以将 [i - zeroNum][j - oneNum] 视为减去物品的重量 weight[i]
字符串的个数 + 1 视为 value[i]

3.初始化

因为物品的价值。即strs的字符串数量不可能为负数，因此初始化为 0 即可。

4.遍历顺序

//1.先遍历字符串,统计当前字符串的 zeroNum 和 oneNum
for(String str : strs){
    int oneNum;
    int zeroNum;
    for(char c : str){
        zeroNum = 0;
        oneNum = 0;
        if('0' == c){
            zeroNum++;
        }else{
            oneNum++;
        }
    }
	//2.后遍历01背包
    //遍历二维背包的容量
    //每个字符串只放一次,不重放，逆序遍历
    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);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5.推演分析

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 3, n = 3 输出：3

注意：背包遍历顺序是逆序遍历，因此这里应该为倒推，从右下角向左上角推导。

---

代码实现

完整代码实现

public int findMaxForm(String[] strs, int m, int n) {
	//m:0的个数,n:1的个数
	if(0 == strs.length) return 0;
	
	//初始化
	int[][] dp = new int[m+1][n+1];
	int zeroNum;
	int oneNum;
	//遍历顺序
	//遍历物品str
	for(String str: strs){ 
		zeroNum = 0;
        oneNum = 0;
        for(char c: str.toCharArray()){
			if('0' == c){
				zeroNum++;
			}else{
				oneNum++;
			}
		}
		//遍历二维背包,逆序遍历
		for(int i = m; i >= zeroNum;i--){
			for(int j = n; j >= oneNum;j--){
				dp[i][j] = Math.max(dp[i][j],dp[i - zeroNum][j - oneNum] + 1);
			}
		}
	}
	return dp[m][n];	
}
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

---

小结

本题考察二维01背包，同样是考察 01 背包，对我们把题目的条件，转化为物品，背包容量，有一定的难度。需要找到其中的关系，将字符串数组中的元素 s 看作物品，将限制条件 m 和 n 转化为背包容量。