343. 整数拆分
DP 五部曲：
- 定义 dp 数组及下标含义：本题定义为拆分数字 i，得到的最大乘积为 dp[i];
- 确定递推公式： dp[i] = max(dp[i], (i - j) * j, dp[i- j] * j} );
- 初始化，dp[0]/dp[1]无意义，可以从 2 开始，dp[2] = 1;
- 确认遍历顺序；
- 举例推导 dp 数组（打印 dp 数组，验证是否符合预期）；
package jjn.carl.dp; import java.util.Scanner; /** * @author Jjn * @since 2023/8/7 23:22 */ public class LeetCode343 { public int integerBreak(int n) { int[] dp = new int[n + 1]; dp[2] = 1; for (int i = 3; i <= n; i++) { for (int j = 1; j < i - 1; j++) { dp[i] = Math.max(dp[i], Math.max((i - j) * j, dp[i - j] * j)); } } return dp[n]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int integerBreak = new LeetCode343().integerBreak(n); System.out.println(integerBreak); } }
96. 不同的二叉搜索树
DP 五部曲：
- 定义 DP 数组含义：dp[i]可以表示为从 1～i 为不同元素节点组成的二叉搜索树的个数；
- 确认递推公式： dp[i] += dp[j - 1] * dp[i - j]
- 初始化 dp 数组，dp[0] = 1
- 确认遍历顺序，因为状态 i 依赖此前的状态，故从 1 开始遍历到 i
- 举例推导 dp 数组，辅助打印确认是否正确。
package jjn.carl.dp; import java.util.Scanner; /** * @author Jjn * @since 2023/8/7 23:53 */ public class LeetCode96 { public int numTrees(int n) { int[] dp = new int[n + 1]; dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int numTrees = new LeetCode96().numTrees(n); System.out.println(numTrees); } }
