题目
image.png
题解
题解1
0-1背包问题
注意索引问题
// 状态：m,n,可选的str
// 选择：
// dp意义 dp[t][i][j] 用i个0j个1共可以拼几个字符串 前t个中
// dp[t][i][j] = max ( dp[t-1][i-t[0]][j-t[1]]+1 t选择(i,j>t[0],t[1]) || dp[t-1][i][j] t不选择 )
// base case dp[...][0][0]=0,
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int nums = strs.length;
int[][] calc = new int[nums+1][2];
int c0 = 0, c1 = 0;
for (int i = 1; i <= nums; i++) {
c0 = 0;
c1 = 0;
for (int j = 0; j < strs[i-1].length(); j++) {
if (strs[i-1].charAt(j) == '0') {
c0++;
} else {
c1++;
}
}
calc[i][0] = c0;
calc[i][1] = c1;
}
int[][][] dp = new int[nums+1][m + 1][n + 1];
for (int t = 1; t <= nums; t++) {
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i < calc[t][0] || j < calc[t][1]) {
dp[t][i][j] = dp[t-1][i][j]; // t-1啊
} else {
dp[t][i][j] = Math.max(dp[t-1][i-calc[t][0]][j-calc[t][1]]+1, dp[t-1][i][j]);
}
}
}
}
return dp[nums][m][n];
}
}
