代码随想录——一和零（Leetcode474）

题目链接

0-1背包

class Solution {public int findMaxForm(String[] strs, int m, int n) {// 本题m，n为背包两个维度// dp[i][j]:最多右i个0和j个1的strs的最大子集大小int[][] dp = new int[m + 1][n + 1];// 遍历strs中字符串for(String str : strs){int num0 = 0;int num1 = 0;for(int i = 0; i < str.length(); i++){if(str.charAt(i) == '0'){num0++;}if(str.charAt(i) == '1'){num1++;}}for(int i = m; i >= num0; i--){for(int j = n; j >= num1; j--){dp[i][j] = Math.max(dp[i][j], dp[i - num0][j - num1] + 1);}}}return dp[m][n];}
}

背包递推公式：dp[i][j] = max(dp[i][j], dp[i - num0][j - num1] + 1)