动态规划---一和零

题目：

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