代码随想录算法训练营Day40 | LeetCode343. 整数拆分、LeetCode96.不同的二叉搜索树

LeetCode343. 整数拆分

这道题如果用数学证明的方法，利用贪心的策略，将数全部拆成3，有余数×4，即可得到最大值，但需要数学证明。

本题用动态规划的思想第一层for循环从小到大遍历数组，dp[i]即为第i个数拆分之后的最大值。第二层for循环，负责拆分数，j控制每次拆出来的数大小，最后取最大值。

动态规划五部曲：dp数组含义；递推公式；初始化；遍历顺序；打印dp数组，本题递推公式比较难想。

代码如下：时间复杂度O(n^2);空间复杂度有O(n)

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/2;j++){
                dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
};

LeetCode96.不同的二叉搜索树

本题思路比较难想，以输入为3分析规律，dp[3]等于头节点为1的树+头节点为2的树+头节点为3的树，那么当确定了头节点时，剩下的左右子树好像和dp[0,1,2]有关系，排列组合可以直接得到，因此可以用动态规划的思想。

递归五部曲：
1、dp[i]数组的含义，为个数；
2、递推公式：确定了头节点后左右子树结果乘积；
3、初始化，本题只初始化dp[0]即可，因为一颗空树也是一颗二叉搜索树，注意这里如果初始化到dp[2]=2,那么在创建数组的时候必须创建大小为n+2的数组，如果小于n+2时，此时输入为1会出现数组溢出。int数组默认初始化为0。
4、遍历顺序：从前往后；
5、打印dp数组。

代码如下：时间复杂度O(n^2)；空间复杂度O(n)

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[i-j]*dp[j-1];
            }
        }
        return dp[n];
    }
};