模板网站建设+百度,能源建设网站,手机 网站 分辨率,网站租空间多少钱一年LeetCode :
343. 整数拆分 - 力扣#xff08;LeetCode#xff09;
1.思路 确定dp[]数组含义#xff0c;dp[n]表示数 n 各子数的最大乘积dp[2] 初始为 1. 遍历顺序#xff0c;从 3 开始#xff0c;最值从 j * (i - j) 和 j * dp[i - j] 以及 dp[i] 中选择.dp[i] Math.ma…LeetCode :
343. 整数拆分 - 力扣LeetCode
1.思路 确定dp[]数组含义dp[n]表示数 n 各子数的最大乘积dp[2] 初始为 1. 遍历顺序从 3 开始最值从 j * (i - j) 和 j * dp[i - j] 以及 dp[i] 中选择.dp[i] Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j])); 2.代码实现 1class Solution {2 public int integerBreak(int n) {3 int[] dp new int[n 1]; // 创建一个长度为 n 1 的数组用于存储每个整数的最大乘积4 dp[2] 1; // 初始化 dp[2] 1 因为 2 只能分解为两个 1 成绩为15 // 从整数 3 开始计算最大乘积6 for (int i 3; i n; i) { 7 // 遍历从 1 到 i - j 的整数 j 表示分解的第一个整数的大小8 for (int j 1; j i - j; j) {9 // 计算当前情况下的最大乘积 有两种情况
10 // 1. 不分解第一个整数乘积为 j * (i - j)
11 // 2. 分解第一个整数乘积为 j * dp[i - j], dp[i - j] 表示将 i - j 分解为多个整数后的最大乘积
12 // 去两者之间的较大值
13 // dp[i] 每次也参与其中
14 dp[i] Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
15 }
16 }
17 // 返回 n 对应的最大乘积
18 return dp[n];
19 }
20}3.复杂度分析 时间复杂度O(n^2). 空间复杂度O(n).
LeetCode:
96. 不同的二叉搜索树 - 力扣LeetCode
1.思路 看完题解这种题更像是找规律。而且未必好找似乎只能靠熟练度刷出思维方式. 动规五部曲 ①确定dp[n]的含义数n的二叉搜索树的个数为dp[n] ②dp[]数组声明int[] dp new int[n 1]; ③初始化dp[0] 1;dp[1] 1; ④确定递推公式dp[i] dp[j - 1] * dp[i - j]; ⑤确定遍历顺序从小数到大数顺序遍历. 2.代码实现 1class Solution {2 public int numTrees(int n) {3 int[] dp new int[n 1];4 dp[0] 1;5 dp[1] 1;6 for (int i 2; i n; i) {7 for (int j 1; j i; j) {8 // 对于第 i 个节点需要考虑 1 作为根节点直到 i 作为根节点的情况所以需要累加9 // 一共 i 个节点根节点为 j 时左子树的节点个数为 j - 1 右子树的节点数量为 i - j
10 dp[i] dp[j - 1] * dp[i - j];
11 }
12 }
13 return dp[n];
14 }
15}3.复杂度分析 时间复杂度O(n^2). 空间复杂度O(n).
