代码随想录算法训练营第四十一天

 343. 整数拆分 

我写的其实有点解释不通dp[0]和dp[1]

class Solution {
public:
    int integerBreak(int n) {
        vector<int>dp(n+1,0);
        if(n == 2)return 1;
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 0;i <= n;i++){
            for(int j = 1;j <= i;j++){
                dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
};

用代码随想录的更好一点，主要的思想其实是j * dp[i-j]这里，然后就是一定会有j * (i-j)两个数的可能性，j * dp[i-j]实际上更偏向于两个及以上的情况，会忽略一些只有两个数的情况，比如4就过不去，因为dp[2] = 1,2*dp[2]实际上是2*1*1。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

class Solution {
public:
    int numTrees(int n) {
        vector<int>dp(n+1,0);
        if(n <= 2)return n;
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i <= n;i++){
            for(int j = 1;j<=i;j++){
                dp[i] += dp[j-1] * dp[i-j];  //左子树个数*右子树个数
            }
        }
        return dp[n];
    }
};