代码随想录 Day41 - 动态规划（二）

2023-08-08
江苏
本文字数：917 字
阅读完需：约 3 分钟

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);    }}

复制代码

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/a8d129991a51067bd8b654841】。

jjn0703

关注

Java工程师/终身学习者 2018-03-26 加入

USTC硕士/健身健美爱好者/Java工程师.

发布

暂无评论

创作场景

代码随想录 Day41 - 动态规划（二）

343. 整数拆分

96. 不同的二叉搜索树

jjn0703

评论