class069 从递归入手三维动态规划
code1 474. 一和零
// 一和零(多维费用背包)
// 给你一个二进制字符串数组 strs 和两个整数 m 和 n
// 请你找出并返回 strs 的最大子集的长度
// 该子集中 最多 有 m 个 0 和 n 个 1
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集
// 测试链接 : https://leetcode.cn/problems/ones-and-zeroes/
dp[i][o][z]：表示str[i…]之后选取不超过o z的子集数量
=max(不选该串，选该串)
不选该串：dp[i+1][o][z]
选该串：1+dp[i+1][o-os][z-zs]
code1 递归
code2 记忆化搜索
code3 动态规划
code4 空间压缩
package class069; // 一和零(多维费用背包) // 给你一个二进制字符串数组 strs 和两个整数 m 和 n // 请你找出并返回 strs 的最大子集的长度 // 该子集中 最多 有 m 个 0 和 n 个 1 // 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 // 测试链接 : https://leetcode.cn/problems/ones-and-zeroes/ public class Code01_OnesAndZeroes { public static int zeros, ones; // 统计一个字符串中0的1的数量 // 0的数量赋值给全局变量zeros // 1的数量赋值给全局变量ones public static void zerosAndOnes(String str) { zeros = 0; ones = 0; for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == '0') { zeros++; } else { ones++; } } } public static int findMaxForm1(String[] strs, int m, int n) { return f1(strs, 0, m, n); } // strs[i....]自由选择，希望零的数量不超过z、一的数量不超过o // 最多能选多少个字符串 public static int f1(String[] strs, int i, int z, int o) { if (i == strs.length) { // 没有字符串了 return 0; } // 不使用当前的strs[i]字符串 int p1 = f1(strs, i + 1, z, o); // 使用当前的strs[i]字符串 int p2 = 0; zerosAndOnes(strs[i]); if (zeros <= z && ones <= o) { p2 = 1 + f1(strs, i + 1, z - zeros, o - ones); } return Math.max(p1, p2); } // 记忆化搜索 public static int findMaxForm2(String[] strs, int m, int n) { int[][][] dp = new int[strs.length][m + 1][n + 1]; for (int i = 0; i < strs.length; i++) { for (int z = 0; z <= m; z++) { for (int o = 0; o <= n; o++) { dp[i][z][o] = -1; } } } return f2(strs, 0, m, n, dp); } public static int f2(String[] strs, int i, int z, int o, int[][][] dp) { if (i == strs.length) { return 0; } if (dp[i][z][o] != -1) { return dp[i][z][o]; } int p1 = f2(strs, i + 1, z, o, dp); int p2 = 0; zerosAndOnes(strs[i]); if (zeros <= z && ones <= o) { p2 = 1 + f2(strs, i + 1, z - zeros, o - ones, dp); } int ans = Math.max(p1, p2); dp[i][z][o] = ans; return ans; } public static int findMaxForm3(String[] strs, int m, int n) { int len = strs.length; int[][][] dp = new int[len + 1][m + 1][n + 1]; for (int i = len - 1; i >= 0; i--) { zerosAndOnes(strs[i]); for (int z = 0, p1, p2; z <= m; z++) { for (int o = 0; o <= n; o++) { p1 = dp[i + 1][z][o]; p2 = 0; if (zeros <= z && ones <= o) { p2 = 1 + dp[i + 1][z - zeros][o - ones]; } dp[i][z][o] = Math.max(p1, p2); } } } return dp[0][m][n]; } public static int findMaxForm4(String[] strs, int m, int n) { // 代表i == len int[][] dp = new int[m + 1][n + 1]; for (String s : strs) { // 每个字符串逐渐遍历即可 // 更新每一层的表 // 和之前的遍历没有区别 zerosAndOnes(s); for (int z = m; z >= zeros; z--) { for (int o = n; o >= ones; o--) { dp[z][o] = Math.max(dp[z][o], 1 + dp[z - zeros][o - ones]); } } } return dp[m][n]; } }
code2 879. 盈利计划
// 盈利计划(多维费用背包)
// 集团里有 n 名员工，他们可以完成各种各样的工作创造利润
// 第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与
// 如果成员参与了其中一项工作，就不能参与另一项工作
// 工作的任何至少产生 minProfit 利润的子集称为 盈利计划
// 并且工作的成员总数最多为 n
// 有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
// 测试链接 : https://leetcode.cn/problems/profitable-schemes/
dp[i][r][s]：表示工作[i…]之后人数剩余r，利润剩余s的方案数
code1 递归
code2 记忆化搜索
code3 动态规划+空间压缩
package class069; // 盈利计划(多维费用背包) // 集团里有 n 名员工，他们可以完成各种各样的工作创造利润 // 第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与 // 如果成员参与了其中一项工作，就不能参与另一项工作 // 工作的任何至少产生 minProfit 利润的子集称为 盈利计划 // 并且工作的成员总数最多为 n // 有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。 // 测试链接 : https://leetcode.cn/problems/profitable-schemes/ public class Code02_ProfitableSchemes { // n : 员工的额度，不能超 // p : 利润的额度，不能少 // group[i] : i号项目需要几个人 // profit[i] : i号项目产生的利润 // 返回能做到员工不能超过n，利润不能少于p的计划有多少个 public static int profitableSchemes1(int n, int minProfit, int[] group, int[] profit) { return f1(group, profit, 0, n, minProfit); } // i : 来到i号工作 // r : 员工额度还有r人，如果r<=0说明已经没法再选择工作了 // s : 利润还有s才能达标，如果s<=0说明之前的选择已经让利润达标了 // 返回 : i.... r、s，有多少种方案 public static int f1(int[] g, int[] p, int i, int r, int s) { if (r <= 0) { // 人已经耗尽了，之前可能选了一些工作 return s <= 0 ? 1 : 0; } // r > 0 if (i == g.length) { // 工作耗尽了，之前可能选了一些工作 return s <= 0 ? 1 : 0; } // 不要当前工作 int p1 = f1(g, p, i + 1, r, s); // 要做当前工作 int p2 = 0; if (g[i] <= r) { p2 = f1(g, p, i + 1, r - g[i], s - p[i]); } return p1 + p2; } public static int mod = 1000000007; public static int profitableSchemes2(int n, int minProfit, int[] group, int[] profit) { int m = group.length; int[][][] dp = new int[m][n + 1][minProfit + 1]; for (int a = 0; a < m; a++) { for (int b = 0; b <= n; b++) { for (int c = 0; c <= minProfit; c++) { dp[a][b][c] = -1; } } } return f2(group, profit, 0, n, minProfit, dp); } public static int f2(int[] g, int[] p, int i, int r, int s, int[][][] dp) { if (r <= 0) { return s == 0 ? 1 : 0; } if (i == g.length) { return s == 0 ? 1 : 0; } if (dp[i][r][s] != -1) { return dp[i][r][s]; } int p1 = f2(g, p, i + 1, r, s, dp); int p2 = 0; if (g[i] <= r) { p2 = f2(g, p, i + 1, r - g[i], Math.max(0, s - p[i]), dp); } int ans = (p1 + p2) % mod; dp[i][r][s] = ans; return ans; } public static int profitableSchemes3(int n, int minProfit, int[] group, int[] profit) { // i = 没有工作的时候，i == g.length int[][] dp = new int[n + 1][minProfit + 1]; for (int r = 0; r <= n; r++) { dp[r][0] = 1; } int m = group.length; for (int i = m - 1; i >= 0; i--) { for (int r = n; r >= 0; r--) { for (int s = minProfit; s >= 0; s--) { int p1 = dp[r][s]; int p2 = group[i] <= r ? dp[r - group[i]][Math.max(0, s - profit[i])] : 0; dp[r][s] = (p1 + p2) % mod; } } } return dp[n][minProfit]; } }
code3 688. 骑士在棋盘上的概率
// 骑士在棋盘上的概率
// n * n的国际象棋棋盘上，一个骑士从单元格(row, col)开始，并尝试进行 k 次移动
// 行和列从0开始，所以左上单元格是 (0,0)，右下单元格是 (n-1, n-1)
// 象棋骑士有8种可能的走法。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格
// 每次骑士要移动时，它都会随机从8种可能的移动中选择一种，然后移动到那里
// 骑士继续移动，直到它走了 k 步或离开了棋盘
// 返回 骑士在棋盘停止移动后仍留在棋盘上的概率
// 测试链接 : https://leetcode.cn/problems/knight-probability-in-chessboard/
code 记忆化搜索
package class069; // 骑士在棋盘上的概率 // n * n的国际象棋棋盘上，一个骑士从单元格(row, col)开始，并尝试进行 k 次移动 // 行和列从0开始，所以左上单元格是 (0,0)，右下单元格是 (n-1, n-1) // 象棋骑士有8种可能的走法。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格 // 每次骑士要移动时，它都会随机从8种可能的移动中选择一种，然后移动到那里 // 骑士继续移动，直到它走了 k 步或离开了棋盘 // 返回 骑士在棋盘停止移动后仍留在棋盘上的概率 // 测试链接 : https://leetcode.cn/problems/knight-probability-in-chessboard/ public class Code03_KnightProbabilityInChessboard { public static double knightProbability(int n, int k, int row, int col) { double[][][] dp = new double[n][n][k + 1]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int t = 0; t <= k; t++) { dp[i][j][t] = -1; } } } return f(n, row, col, k, dp); } // 从(i,j)出发还有k步要走，返回最后在棋盘上的概率 public static double f(int n, int i, int j, int k, double[][][] dp) { if (i < 0 || i >= n || j < 0 || j >= n) { return 0; } if (dp[i][j][k] != -1) { return dp[i][j][k]; } double ans = 0; if (k == 0) { ans = 1; } else { ans += (f(n, i - 2, j + 1, k - 1, dp) / 8); ans += (f(n, i - 1, j + 2, k - 1, dp) / 8); ans += (f(n, i + 1, j + 2, k - 1, dp) / 8); ans += (f(n, i + 2, j + 1, k - 1, dp) / 8); ans += (f(n, i + 2, j - 1, k - 1, dp) / 8); ans += (f(n, i + 1, j - 2, k - 1, dp) / 8); ans += (f(n, i - 1, j - 2, k - 1, dp) / 8); ans += (f(n, i - 2, j - 1, k - 1, dp) / 8); } dp[i][j][k] = ans; return ans; } }
code4 2435. 矩阵中和能被 K 整除的路径
// 矩阵中和能被 K 整除的路径
// 给一个下标从0开始的 n * m 整数矩阵 grid 和一个整数 k
// 从起点(0,0)出发，每步只能往下或者往右，你想要到达终点(m-1, n-1)
// 请你返回路径和能被 k 整除的路径数目
// 由于答案可能很大，返回答案对10^9+7取余的结果
// 测试链接 : https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k/
code1 递归
code2 记忆化搜索
code3 动态规划
package class069; // 矩阵中和能被 K 整除的路径 // 给一个下标从0开始的 n * m 整数矩阵 grid 和一个整数 k // 从起点(0,0)出发，每步只能往下或者往右，你想要到达终点(m-1, n-1) // 请你返回路径和能被 k 整除的路径数目 // 由于答案可能很大，返回答案对10^9+7取余的结果 // 测试链接 : https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k/ public class Code04_PathsDivisibleByK { public static int mod = 1000000007; public static int numberOfPaths1(int[][] grid, int k) { int n = grid.length; int m = grid[0].length; return f1(grid, n, m, k, 0, 0, 0); } // 当前来到(i,j)位置，最终一定要走到右下角(n-1,m-1) // 从(i,j)出发，最终一定要走到右下角(n-1,m-1)，有多少条路径，累加和%k的余数是r public static int f1(int[][] grid, int n, int m, int k, int i, int j, int r) { if (i == n - 1 && j == m - 1) { return grid[i][j] % k == r ? 1 : 0; } // 后续需要凑出来的余数need int need = (k + r - (grid[i][j] % k)) % k; int ans = 0; if (i + 1 < n) { ans = f1(grid, n, m, k, i + 1, j, need); } if (j + 1 < m) { ans = (ans + f1(grid, n, m, k, i, j + 1, need)) % mod; } return ans; } public static int numberOfPaths2(int[][] grid, int k) { int n = grid.length; int m = grid[0].length; int[][][] dp = new int[n][m][k]; for (int a = 0; a < n; a++) { for (int b = 0; b < m; b++) { for (int c = 0; c < k; c++) { dp[a][b][c] = -1; } } } return f2(grid, n, m, k, 0, 0, 0, dp); } public static int f2(int[][] grid, int n, int m, int k, int i, int j, int r, int[][][] dp) { if (i == n - 1 && j == m - 1) { return grid[i][j] % k == r ? 1 : 0; } if (dp[i][j][r] != -1) { return dp[i][j][r]; } int need = (k + r - grid[i][j] % k) % k; int ans = 0; if (i + 1 < n) { ans = f2(grid, n, m, k, i + 1, j, need, dp); } if (j + 1 < m) { ans = (ans + f2(grid, n, m, k, i, j + 1, need, dp)) % mod; } dp[i][j][r] = ans; return ans; } public static int numberOfPaths3(int[][] grid, int k) { int n = grid.length; int m = grid[0].length; int[][][] dp = new int[n][m][k]; dp[n - 1][m - 1][grid[n - 1][m - 1] % k] = 1; for (int i = n - 2; i >= 0; i--) { for (int r = 0; r < k; r++) { dp[i][m - 1][r] = dp[i + 1][m - 1][(k + r - grid[i][m - 1] % k) % k]; } } for (int j = m - 2; j >= 0; j--) { for (int r = 0; r < k; r++) { dp[n - 1][j][r] = dp[n - 1][j + 1][(k + r - grid[n - 1][j] % k) % k]; } } for (int i = n - 2, need; i >= 0; i--) { for (int j = m - 2; j >= 0; j--) { for (int r = 0; r < k; r++) { need = (k + r - grid[i][j] % k) % k; dp[i][j][r] = dp[i + 1][j][need]; dp[i][j][r] = (dp[i][j][r] + dp[i][j + 1][need]) % mod; } } } return dp[0][0][0]; } }
code5 87. 扰乱字符串
// 扰乱字符串
// 使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
// 步骤1 : 如果字符串的长度为 1 ，算法停止
// 步骤2 : 如果字符串的长度 > 1 ，执行下述步骤：
// 在一个随机下标处将字符串分割成两个非空的子字符串
// 已知字符串s，则可以将其分成两个子字符串x和y且满足s=x+y
// 可以决定是要 交换两个子字符串 还是要 保持这两个子字符串的顺序不变
// 即s可能是 s = x + y 或者 s = y + x
// 在x和y这两个子字符串上继续从步骤1开始递归执行此算法
// 给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串
// 如果是，返回true ；否则，返回false
// 测试链接 : https://leetcode.cn/problems/scramble-string/
code1 递归
code2 递归优化
code3 记忆化搜索
code4 动态规划
package class069; // 扰乱字符串 // 使用下面描述的算法可以扰乱字符串 s 得到字符串 t ： // 步骤1 : 如果字符串的长度为 1 ，算法停止 // 步骤2 : 如果字符串的长度 > 1 ，执行下述步骤： // 在一个随机下标处将字符串分割成两个非空的子字符串 // 已知字符串s，则可以将其分成两个子字符串x和y且满足s=x+y // 可以决定是要 交换两个子字符串 还是要 保持这两个子字符串的顺序不变 // 即s可能是 s = x + y 或者 s = y + x // 在x和y这两个子字符串上继续从步骤1开始递归执行此算法 // 给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串 // 如果是，返回true ；否则，返回false // 测试链接 : https://leetcode.cn/problems/scramble-string/ public class Code05_ScrambleString { public static boolean isScramble1(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int n = s1.length; return f1(s1, 0, n - 1, s2, 0, n - 1); } // s1[l1....r1] // s2[l2....r2] // 保证l1....r1与l2....r2 // 是不是扰乱串的关系 public static boolean f1(char[] s1, int l1, int r1, char[] s2, int l2, int r2) { if (l1 == r1) { // s1[l1..r1] // s2[l2..r2] return s1[l1] == s2[l2]; } // s1[l1..i][i+1....r1] // s2[l2..j][j+1....r2] // 不交错去讨论扰乱关系 for (int i = l1, j = l2; i < r1; i++, j++) { if (f1(s1, l1, i, s2, l2, j) && f1(s1, i + 1, r1, s2, j + 1, r2)) { return true; } } // 交错去讨论扰乱关系 // s1[l1..........i][i+1...r1] // s2[l2...j-1][j..........r2] for (int i = l1, j = r2; i < r1; i++, j--) { if (f1(s1, l1, i, s2, j, r2) && f1(s1, i + 1, r1, s2, l2, j - 1)) { return true; } } return false; } // 依然暴力尝试，只不过四个可变参数，变成了三个 public static boolean isScramble2(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int n = s1.length; return f2(s1, s2, 0, 0, n); } public static boolean f2(char[] s1, char[] s2, int l1, int l2, int len) { if (len == 1) { return s1[l1] == s2[l2]; } // s1[l1.......] len // s2[l2.......] len // 左 : k个 右: len - k 个 for (int k = 1; k < len; k++) { if (f2(s1, s2, l1, l2, k) && f2(s1, s2, l1 + k, l2 + k, len - k)) { return true; } } // 交错！ for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++) { if (f2(s1, s2, l1, j, k) && f2(s1, s2, i, l2, len - k)) { return true; } } return false; } public static boolean isScramble3(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int n = s1.length; // dp[l1][l2][len] : int 0 -> 没展开过 // dp[l1][l2][len] : int -1 -> 展开过，返回的结果是false // dp[l1][l2][len] : int 1 -> 展开过，返回的结果是true int[][][] dp = new int[n][n][n + 1]; return f3(s1, s2, 0, 0, n, dp); } public static boolean f3(char[] s1, char[] s2, int l1, int l2, int len, int[][][] dp) { if (len == 1) { return s1[l1] == s2[l2]; } if (dp[l1][l2][len] != 0) { return dp[l1][l2][len] == 1; } boolean ans = false; for (int k = 1; k < len; k++) { if (f3(s1, s2, l1, l2, k, dp) && f3(s1, s2, l1 + k, l2 + k, len - k, dp)) { ans = true; break; } } if (!ans) { for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++) { if (f3(s1, s2, l1, j, k, dp) && f3(s1, s2, i, l2, len - k, dp)) { ans = true; break; } } } dp[l1][l2][len] = ans ? 1 : -1; return ans; } public static boolean isScramble4(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int n = s1.length; boolean[][][] dp = new boolean[n][n][n + 1]; // 填写len=1层，所有的格子 for (int l1 = 0; l1 < n; l1++) { for (int l2 = 0; l2 < n; l2++) { dp[l1][l2][1] = s1[l1] == s2[l2]; } } for (int len = 2; len <= n; len++) { // 注意如下的边界条件 : l1 <= n - len l2 <= n - len for (int l1 = 0; l1 <= n - len; l1++) { for (int l2 = 0; l2 <= n - len; l2++) { for (int k = 1; k < len; k++) { if (dp[l1][l2][k] && dp[l1 + k][l2 + k][len - k]) { dp[l1][l2][len] = true; break; } } if (!dp[l1][l2][len]) { for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++) { if (dp[l1][j][k] && dp[i][l2][len - k]) { dp[l1][l2][len] = true; break; } } } } } } return dp[0][0][n]; } }
