题目:
给你一个二进制字符串数组 strs
和两个整数 m
和 n
。
请你找出并返回 strs
的最大子集的长度,该子集中 最多 有 m
个 0
和 n
个 1
。
如果 x
的所有元素也是 y
的元素,集合 x
是集合 y
的 子集 。
思路:
动态规划五部曲:
1.确定dp数组及含义
dp数组需要有两个维度,i来遍历数字0,j来遍历数字1。dp[i][j]表示最多有i个数字0,j个数字1时最大子集的长度。
2.确定递推公式
dp[i][j]可以由前一个str里的字符串推导出来,str里的字符串有zeroNum个0,oneNum个1
dp[i][j]就可以是dp[i-zeroNum][j-oneNum]+1
在遍历过程中取最大值,所以递推公式为dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)
3.dp数组初始化
全初始化为0即可。
4.确定遍历顺序
外层for正序循环遍历物品(字符串),内层for循环倒序遍历背包容量(m和n)。
5.举例推导dp数组
strs = ["10", "0001", "111001", "1", "0"], m = 3, n = 3
dp[i][j]=[[0,1,1,1],
[1,2,2,2],
[1,2,3,3],
[1,2,3,3]]
代码:
public int findMaxForm(String[] strs, int m, int n) {int[][] dp=new int[m+1][n+1];int zeroNum,oneNum;for(String s:strs){oneNum=0;zeroNum=0;for(char c:s.toCharArray()){if(c=='0')zeroNum++;elseoneNum++;}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];}