一、LeetCode343. 整数拆分
题目链接:343. 整数拆分
题目描述:
给定一个正整数 n
,将其拆分为 k
个 正整数 的和( k >= 2
),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
算法分析:
定义dp数组及下标含义:
dp[i]表述正整数i拆分成k个正整数乘积所能够得到的最大值。
递推公式:
用一个j来遍历从1到i,得到两个dp[i],即dp[i]=j*(i-j)(将整数i分成两个正整数j和i-j),和dp[i]=j*dp[i-j]。
所以dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]))。
初始化:
dp[0]和dp[1]初始化没有意义,所以我们初始化dp[2]=1(2拆分成两个1相乘)。
遍历顺序:
因为dp[2]已经初始化了,所以我们从3遍历到n。
代码如下:
class Solution {
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; j++) {
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
}
时间复杂度o(n^2),空间复杂度o(n)。
二、LeetCode96. 不同的二叉搜索树
题目链接:96. 不同的二叉搜索树
题目描述:
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3 输出:5
示例 2:
输入:n = 1 输出:1
提示:
1 <= n <= 19
算法分析:
定义dp数组及下标含义:
dp[i]表示i个节点组成的二叉搜索树的种树。
递推公式:
j从1遍历到i,当j为头节点时,左子树有i-1个节点,左子树的种类数相当于dp[j-1],右子树有i-j个节点,右子树的种类数相当于dp[i-j]。
所以dp[i]+=dp[j-1]*dp[i-j],j从1比那里遍历到i;
初始化:
dp[0]初始化为1(0的话会影响乘法结果),dp[1]初始化为1(一个节点的二叉搜索树只有一种情况)
遍历顺序:
i从2遍历到n,然后确定dp[i](dp[i]+=dp[j-1]*dp[i-j])。
如果结果有误打印dp数组检查验证。
代码如下:
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
时间复杂度o(n^2),空间复杂度o(n)文章来源:https://www.toymoban.com/news/detail-761482.html
总结
这两道题还是比较难的,自己想很难有思路。文章来源地址https://www.toymoban.com/news/detail-761482.html
到了这里,关于LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!