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]; }}