> 文档中心 > 474. 一和零

474. 一和零


思路

首先,这个题是有两个容量的背包问题。分别是容量为m,和容量为n的背包。这点是和其他题目不同的地方。

运用动态规划五部曲。

1.确定dp数组

dp[i][j]表示有i个0和j个1的背包中,所装的字符串的个数。

2.递推公式

dp[i][j] = Math.max(dp[i][j],dp[i-zeroNumber][j-oneNumber]+1);

此处的+1是因为,如果当前字符串放入背包则背包中字符串的个数将会+1;

3.dp数组初始化

根据dp数组的定义就可以知道dp[0][0]=0

4.确定遍历顺序

可以根据递推公式知道,dp[i][j]与其前面的元素有关,所以应该是前序遍历,但是背包容量应该后序遍历,防止物品的重复放入。又因为本题的i和j都是背包容量,所以都是后序遍历。

5.打印dp数组

数组的最后一个元素就是最后的结果。

代码

class Solution {    public int findMaxForm(String[] strs, int m, int n) { int dp[][] = new int[m+1][n+1]; dp[0][0] = 0; for(String str:strs){     int zeroNumber = 0;     int oneNumber = 0;     for(char c:str.toCharArray()){  if(c=='0'){      zeroNumber++;  }  if(c=='1'){      oneNumber++;  }     }     for(int i = m;i>=zeroNumber;i--){  for(int j = n;j>=oneNumber;j--){      dp[i][j] = Math.max(dp[i][j],dp[i-zeroNumber][j-oneNumber]+1);  }     } } return dp[m][n];    }}