网站 数据库 模板,网站系统建设合作合同范本,石家庄 网站 科技,做网站需要许可证吗文档讲解#xff1a;整数拆分 不同的二叉搜索树 343.整数拆分
题目链接#xff1a;https://leetcode.cn/problems/integer-break/description/
思路#xff1a; 题目要求我们拆分n#xff0c;拆成k个数使其乘积和最大#xff0c;然而题目中并没有给出k#xff0c;所以… 文档讲解整数拆分 不同的二叉搜索树 343.整数拆分
题目链接https://leetcode.cn/problems/integer-break/description/
思路 题目要求我们拆分n拆成k个数使其乘积和最大然而题目中并没有给出k所以拆分个数不能作为维度来使用。 那我们就设dp[i]表示拆分i能获得的最大乘积则最终答案为dp[n]同时初始状态为dp[1]0,dp[2]1。 那我们在求dp[i]时可以枚举两个数的和为i。即枚举一个jj从1到i-1则获得ij(i-j)。 则dp[i]max(dp[i],j*dp[i-j]); 但这种写法少考虑了一种情况就是j*(i-j)即dp[i]直接拆分成两个数。 因此总的状态转移方程为dp[i]max(dp[i],j*max(i-j,dp[i-j])); 按照上述方法先枚举i再枚举j最后就能求出dp[n]即解决这道题目了。
核心代码
class Solution {
public:int integerBreak(int n) {int dp[60];//dp[i]表示和为i时可以获得的最大乘积for(int i1;in;i) dp[i]i-1;dp[1]1;for(int i3;in;i)for(int j1;ji;j){dp[i]max(dp[i],j*max(i-j,dp[i-j]));}return dp[n];}
};
96.不同的二叉搜索树
题目链接https://leetcode.cn/problems/unique-binary-search-trees/description/
思路 题目给我们一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种。 其实值是多少并不重要重点是我们知道每个数都不相同这就不影响我们的结果。 很明显我们能够意识到n个点要由更少的点来推所以我们朴素的想法是先设状态设dp[n]表示有n个点时不同的二叉搜索树的个数。初始状态为dp[0]1,dp[1]1。假设现在我们知道dp[1]至dp[n-1]了下面考虑怎么求dp[n] 什么时候树不同呢根节点不同时树一定不同。因此我们依次让1到n为根节点求其不同二叉搜索树个数即可 1为根节点时左子树有n-1个点右子树有0个点不同的二叉搜索树个数为dp[n-1]*dp[0]。 2为根节点时左子树有n-2个点右子树有1个点不同的二叉搜索树个数为dp[n-2]*dp[1]。 …… n为根节点时左子树有0个点右子树有n-1个点不同的二叉搜索树个数为dp[0]*dp[n-1]。 统计上面n种情况的和即可求出dp[n]。同时根据上面的分析我们也可以得到规律 根据上述状态转移方程和初始状态枚举推导即可。
核心代码
class Solution {
public:int numTrees(int n) {int dp[20];memset(dp,0,sizeof(dp));dp[0]dp[1]1;for(int i2;in;i)for(int j0;ji;j) dp[i]dp[j]*dp[i-j-1];return dp[n];}
};
今日总结 今日学习时长2h题难度还算可以都做出来了。 接着冲击八股文。
