代码随想录day41

343. 整数拆分 

明确dp数组的含义：dp[i]表示拆分i所能得到的最大乘积。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[0]=0;
        dp[1]=0;
        dp[2]=1;
        for(int i=3;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];
    }
};

因为把i拆分成尽可能相似的数才有可能出现最大的乘积，所以优化思路为j的遍历结束条件为<=i/2.

96.不同的二叉搜索树

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];//当前的根节点是j
            }
        }
        return dp[n];
    }
};

错因：遍历到j的时候，此时根节点就是j，所以应该写dp[j-1]而不是dp[i-1]