代码随想录算法训练营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]。同时根据上面的分析我们也可以得到规律：

$dp[n]=\sum_{0}^{n-1}{dp[j]*dp[n-1-j]}$

根据上述状态转移方程和初始状态，枚举推导即可。

核心代码：

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