本文主要是介绍代码随想录算法训练营29期Day41|LeetCode 343,96,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文档讲解:整数拆分 不同的二叉搜索树
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。即枚举一个j,j从1到i-1,则获得i=j+(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 i=1;i<=n;i++) dp[i]=i-1;dp[1]=1;for(int i=3;i<=n;i++)for(int j=1;j<i;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 i=2;i<=n;i++)for(int j=0;j<i;j++) dp[i]+=dp[j]*dp[i-j-1];return dp[n];}
};
今日总结
今日学习时长2h,题难度还算可以,都做出来了。
接着冲击八股文。
这篇关于代码随想录算法训练营29期Day41|LeetCode 343,96的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!