代码随想录算法训练营第四十天 | LeetCode 343. 整数拆分、96. 不同的二叉搜索树

代码随想录算法训练营第四十天 | LeetCode 343. 整数拆分、96. 不同的二叉搜索树

文章链接：整数拆分        不同的二叉搜索树

视频链接：整数拆分        不同的二叉搜索树

1. LeetCode 343. 整数拆分

1.1 思路

1. 给我们一个数，如何去拆成若干个数使其相乘最大？应该尽可能给他拆成相同的数。比如 10 拆成 5*5<3*3*4。因此拆成 m 个数，这 m 个数数值是近似相等的，这样相乘才尽可能大。
2. 确定 dp 数组及其下标的含义：dp[i]：对 i 进行拆分，得到的这个最大乘积就是 dp[i]
3. 递推公式：如果拆成两个数就是一个 j，一个（i-j）。如果是拆成三个及以上的话，就是 j*dp[i-j]。这里可能疑惑为什么不拆分 j 而是拆分 （i-j）呢？其实这里固定 j 之后 拆分（i-j）就已经包含了所有的情况了包括拆分 j 的情况。
4. dp 数组的初始化：dp[0]、dp[1] 没有意义，拆不了，也可以初始化为 0。dp[2]=1
5. 遍历顺序：从 3 开始往后遍历，两层 for循环。for（int i=3；i<=n；i++）for（int j=1；j<i；i++）递推公式 dp[i]=Math.max（j*(i-j)，j*dp[i-j]，dp[i]）。为什么还需要 dp[i] 呢？dp[i] 的最大值并不一定出现在最后一次拆分中，可能中间某一次拆分就会出现最大值，所以需要再和 dp[i] 取下最值
6. 打印 dp 数组：主要用于 debug

1.2 代码

class Solution {
    public int integerBreak(int n) {
        //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i-j; j++) {
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
                //并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
    }
}

2. LeetCode 96. 不同的二叉搜索树

2.1 思路

1. 
2. 我们看上图可以发现当 n=3 时，我们以 1 为头节点时右子树的布局和 n=2 时是一样的，以 2 为头节点时左子树和右子树的布局和 n=1 时是一样的，以 3 为头节点时左子树的布局和 n=2 时是一样的。因此可以发现 n=3 的情况是可以由 n=1 和 n=2 推导出来
3. 我们再看看 n=3 时二叉搜索树有几种结果。我们可以发现 n=3 时的二叉搜索树的数量是由 n=0、n=1、n=2 推导出来的。即 dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0]
4. 确定 dp 数组及其下标的含义：dp[i]：1 到 i 为节点组成的二叉搜索树的个数为 dp[i]
5. 递推公式：我们用 j 来枚举，从 1 遍历到 i，如果以 j 为头节点，左子树应该有 j-1 个，因为是二叉搜索树，右子树应该有 i-j 个，可以自己举例看看。又以 j-1 个和 i-j 个看 dp，因此 dp[i]+=dp[j-1]*dp[i-j]。这里怎么跟 dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0] 不一样呢？因为这个公式其实就是由那个算出来的
6. dp 数组的初始化：dp[0]=1，因为二叉搜索树也是 1 个
7. 遍历顺序：从前往后从小到大遍历。for（int i=1；i<=n；i++）for（int j=1；j<=i；j++）dp[i]+=dp[j-1]*dp[i-j]
8. 打印 dp 数组：用于 debug

2.2 代码

class Solution {
    public int numTrees(int n) {
        //初始化 dp 数组
        int[] dp = new int[n + 1];
        //初始化0个节点和1个节点的情况
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                //对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
                //一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}