代码随想录day41【动态规划】整数拆分 不同的二叉搜索树

整数拆分

力扣题目链接
分析：
尽量将数拆成相等的数，乘积最大。

1. dp数组含义：dp[i]：分拆数字i的最大乘积
2. 递推公式：
   dp[i] 两种拆法求得最大值：

• 拆两个，j * (i - j) 直接相乘
• 拆多个，j*dp[i-j]

3. 初始化
   只需要初始化 dp[2] = 1。因为dp[0] dp[1]根据dp数组含义，无意义
4. 遍历顺序
   顺序

var integerBreak = function(n) {
    let dp = new Array(n + 1).fill(0)
    dp[2] = 1
    for(let i=3;i<=n;i++){
        for(let j=1;j<=i;j++){
            dp[i]=Math.max(dp[i],j*dp[i-j],(i-j)*j)
        }
    }
    return dp[n]
};

优化：
j 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，因为拆出相似的数得到最大值。

不同的二叉搜索树

力扣题目链接
分析：

1. dp数组含义
   dp[i] ： 1到i为节点组成的二叉搜索树的个数。
2. 递推公式
   dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量（注意：一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j）
3. 初始化
   dp[0] = 1
   否则，若为0，dp[1]结果为0了
4. 遍历顺序
   顺序。
   每个节点的状态依赖前面的节点

var numTrees = function(n) {
    let dp = new Array(n+1).fill(0);
    dp[0] = 1;
    
    for(let i=1;i<=n;i++){
        for(let j=1;j<=i;j++){
            dp[i] +=dp[j-1]*dp[i-j]
        }
    }
    return dp[n]
};