代码随想录算法训练营第41天 | 343.整数拆分, 96.不同的二叉搜索树

343.整数拆分

代码随想录链接

题目

LeetCode-343.整数拆分

给定一个正整数, 返回将该正整数分拆之后各个数之积的最大值.

自己的想法

还是递推, 递推公式可以为\(dp[i]=max((i - j) * j, dp[i - j] * j)\), 其中dp代表的意思是i分拆之后各数之积的最大值.

题解

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n; i++)    // 从i等于3开始计算
            for (int j = 1; j <= i / 2; j++)    // 计算到i/2, 省略另一半重复的计算
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
        return dp[n];
    }
};

96.不同的二叉搜索树

代码随想录链接

题目

LeetCode-96.不同的二叉搜索树

给定一个整数n, 求由n个值为1到n的节点组成的互不相同的二叉搜索树有几种.

自己的想法

二叉搜索树的每一个子树也都是二叉搜索树，利用这一点可以得到递推公式\(dp[i]+=dp[i-j]*dp[j-1]\),其中\(dp[i]\)表示以\(i\)为头节点的树的数量.

题解

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++)    // 根据递推公式计算
            for (int j = 1; j <= i; j++)    // 计算所有左右子树可能的组合数
                dp[i] += dp[j - 1] * dp[i - j];
        return dp[n];
    }
};