算法刷题记录 Day35

算法刷题记录 Day35

Date: 2024.04.01

lc 96. 不同的二叉搜索树

class Solution {
public:
    int numTrees(int n) {
        if(n <= 2)
            return n;
            
        // 二叉搜索树：左结点小于根结点，右结点大于根结点；
        vector<int> dp(n+1, 0);
        // dp[i]表示由i个结点的二叉搜索树有多少种；
        // dp[i] = for(int t=1; t<=i; t++){ dp[i] += dp[t-1] * dp[i-t]}    t为根结点的值
        // dp[0] = 0; dp[1] = 1; dp[2] = 2;
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=n; i++){
            for(int t=1; t<=i; t++){
                dp[i] += (dp[t-1] * dp[i-t]);
            }
        }
        return dp[n];
    }
};

lc 343. 整数拆分

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1, 0);
        // dp[i] 表示整数i所能获得的最大拆分后乘积值；
        // dp[i] = for(int t=1; t<i; t++){max(t*(i-t), t*dp[i-t])};
        // dp[1] = 1;
        for(int i=1; i<=n; i++){
            for(int t=1; t<i; t++){
                dp[i] = max(dp[i], max(t*(i-t), t*dp[i-t]));
            }
        }
        return dp[n];
    }
};