给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。
示例 1:
输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出:4
解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。
示例 2:
输入:strs = ["10", "0", "1"], m = 1, n = 1
输出:2
解释:最大的子集是 {"0", "1"} ,所以答案是 2 。
暴力递归
public int findMaxForm(String[] strs, int m, int n) { return process(strs,m,n,0,0,0); } /** * 暴力尝试 * @param strs 原数组 * @param m 0的个数不超过m * @param n 1的个数不超过n * @param index 当前的选择 * @param sum_1 1的个数 * @param sum_0 0的个数 * @return */ private int process(String[] strs, int m, int n, int index, int sum_1, int sum_0) { //没有可选择的了 if (index == strs.length) { return 0; } //当前的选择超过了指定的个数 if (sum_0 > m && sum_1 > n) { return 0; } //不选当前的数 int p1 = process(strs, m, n, index + 1, sum_1, sum_0); //选当前的数的话,先算一下当前的1和0的个数 String s = strs[index]; int sum1 = 0; int sum0 = 0; for (char c : s.toCharArray()) { if (c == '0') { sum0++; } if (c == '1') { sum1++; } } int p2 = Integer.MIN_VALUE; //如果有有效的选择则做这个决定 if (sum0 + sum_0 <= m && sum1 + sum_1 <= n) { p2 = process(strs, m, n, index + 1, sum_1 + sum1, sum_0 + sum0) + 1; } //选最大的 return Math.max(p1, p2); }
根据以上的递归尝试转动态规划:以下几个原则
1、有几个可变参数,则设几维表
2、根据basecase填好初始表
3、根据递归逻辑写状态转移(即填好表的普通位置)
4、返回看主方法是如何调递归尝试的
public int findMaxForm(String[] strs, int m, int n) { return process2dp(strs, m, n); } private int process2dp(String[] strs, int m, int n) { // index 0---strs.length(). sum0. 0---m sum1 0---n int N = strs.length; int[][][] dp = new int[N + 1][m + 1][n + 1]; for (int i = N - 1; i >= 0; i--) { for (int j = 0; j <= m; j++) { for (int k = 0; k <= n; k++) { int p1 = dp[i + 1][j][k]; String s = strs[i]; int sum1 = 0; int sum0 = 0; for (char c : s.toCharArray()) { if (c == '0') { sum0++; } if (c == '1') { sum1++; } } int p2 = Integer.MIN_VALUE; if (sum0 + j <= m && sum1 + k <= n) { p2 = dp[i + 1][sum0 + j][sum1 + k] + 1; } dp[i][j][k] = Math.max(p1, p2); } } } return dp[0][0][0]; }