今日任务：

1. LeetCode343 整数拆分
2. LeetCode96 不同的二叉搜索树

资料来源：

1. 代码随想录 | LeetCode343 整数拆分
2. 代码随想录 | LeetCode96 不同的二叉搜索树

1 LeetCode343 整数拆分

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

先明确dp数组的含义：对于下标i，dp[i]所储存的就是数字i的拆分数字的乘积最大值。它的递推思路就是，对于每个数字i来说，它都需要进行下一层从1到i- 1的循环j，每次循环都要比较当前已经存储的最大乘积，j * (i - j)（仅分拆一次）和j * (i - j)位置的最大乘积。

举例来说，对于数字4，它所需要在循环中查找的就是：

1 * 3 -> 这个代表分拆成两个数字
1 * dp[3] -> 注意dp[3]的含义：数字3的拆分数字的成绩最大值 这个代表分拆成多个数字
2 * 2
2 * dp[2] 注意 从中间数字开始之后的循环时可以优化的
3 * 1
3 * dp[1]

go
func integerBreak(n int) int {
    dp_array := make([]int, n+1)
    dp_array[2] = 1
    for i := 3; i <= n; i++ {
        for j := 1; j < i; j++ { // 第二层循环 这个循环从1还是从2开始都可以 因为分拆1必然不可能是最大值
            dp_array[i] = max(dp_array[i], j*(i-j), j*dp_array[i-j])
        }
    }

    return dp_array[n]
}

java
class Solution {
    public int integerBreak(int n) {
        int[] dp_array = new int[n + 1];
        dp_array[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp_array[i] = Integer.max(dp_array[i], Integer.max(j * (i - j), j * dp_array[i - j]));
            }
        }
        return dp_array[n];
    }
}

python
class Solution:
    def integerBreak(self, n: int) -> int:
        dp_array = [0] * (n + 1)
        dp_array[2] = 1
        for i in range(3, n + 1):
            for j in range(2, i):
                dp_array[i] = max(dp_array[i], j * (i - j), j * dp_array[i - j])
        return dp_array[n]

2 LeetCode96 不同的二叉搜索树

输入：n = 3
输出：5

输入：n = 1
输出：1

这个题可以被转化为：n个节点组成二叉树的可能的树的形状有多少。还是先明确dp数组的含义：对于下标i，dp[i]表示i个节点组成的互不相同的树的种类。再说递推关系：如果按照题意理解，那么对于任意的节点数量n，它有可能组成的搜索二叉树的种类数量包括从数字1开始到数字n作为根节点的所有搜索二叉树，每个根节点对应的左子树和右子树的数量分别为j和i - 1 - j（j >= 0）。

举例来说，如果要求的n为4时，它所能组成的搜索二叉树如下：

可知dp数组元素之间的递推关系。

go
func numTrees(n int) int {
    dp_array := make([]int, n+1)
    dp_array[0] = 1
    for i := 1; i <= n; i++ { // 针对每个节点数
        for j := 1; j <= i; j++ { // 对于每个节点数i来说 要算的是0 * (i - 1)循环到(i - 1) * 0
            dp_array[i] += dp_array[j-1] * dp_array[i-j]
        }
    }

    return dp_array[n]
}

java
class Solution {
    public int numTrees(int n) {
        int[] dp_array = new int[n + 1];
        dp_array[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) { // 0 * i - 1 到i - 1 * 0
                dp_array[i] += dp_array[j] * dp_array[i - 1 - j];
            }
        }

        return dp_array[n];
    }
}

python
class Solution:
    def numTrees(self, n: int) -> int:
        dp_array = [0] * (n + 1)
        dp_array[0] = 1
        for i in range(1, n + 1):
            for j in range(0, i):
                dp_array[i] += dp_array[j] * dp_array[i - 1 - j]
        return dp_array[n]