这两个题目的分析思路是十分类似的。都是进行一个拆分。

1.不同的二叉搜索树 题目描述：

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：

输入：n = 3
输出：5

思路分析：

动态规划分析：

1. 确定状态：
   令dp[i]表示以1到i为节点值的二叉搜索树的个数。
   初始状态：显然当i = 0时，空树也是一种有效的二叉搜索树，dp[0] = 1。当i = 1时，只有一个节点，dp[1] = 1。
2. 状态转移方程：
   对于dp[i]，我们可以通过选择一个数字作为根节点来构造二叉搜索树。我们可以选择1到i中的任意一个数字作为根节点。假设我们选择了数字k作为根节点，那么：

左子树：其节点值在[1, k-1]之间，左子树可以构造dp[k-1]个不同的树。
右子树：其节点值在[k+1, i]之间，右子树可以构造dp[i-k]个不同的树。
因此，对于每个k（根节点），总的树的个数是左子树树的个数与右子树树的个数的乘积。对于所有k的选择（从1到i），我们将这些结果累加。

综上，状态转移方程为：

这里，dp[k-1]表示k左边的树的个数，dp[i-k]表示k右边的树的个数。因为左子树不动，右子树的任何一种情况都对应一个新的BST，所以用乘法。

1. 时间复杂度：
   对于每个i，我们需要计算dp[i]，而每个dp[i]需要遍历k从1到i，进行dp[k-1] * dp[i-k]的累加，因此时间复杂度为O(n^2)。
2. 空间复杂度：
   我们只需要一个数组dp来保存从0到n的结果，因此空间复杂度为O(n)。

点击查看代码

func numTrees(n int) int {
    dp := make([]int, n+1)
    dp[0] = 1 // 空树有 1 种
    dp[1] = 1 // 只有一个节点的树也有 1 种
    //dp[2] = 2 // 2 个节点可以有 2 种不同的二叉搜索树

    // 计算 dp[i]，表示有 i 个节点时的不同 BST 数量
    for i := 2; i <= n; i++ {
        for j := 1; j <= i; j++ {
            dp[i] += dp[j-1] * dp[i-j]
        }
    }

    return dp[n]
}

整数拆分 2.题目描述

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:

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

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

思路分析

1. 确定状态
   令 \(dp[i]\) 表示将整数\(i\)拆分成至少两个正整数后，这些数的最大乘积。
   我们的目标是求出 $dp[n] $。
2. 状态转移方程
   考虑整数 \(i\)的一种拆分方法：将其分为两个部分 \(j\)和 \(i-j\), 其中 \(1≤j<i\)。

对于这种拆分：

• j 的选择直接影响结果。
• 对于 i−j，可以选择进一步拆分，或者直接保留。
  因此：
  

点击查看代码

func integerBreak(n int) int {
    dp := make([]int, n+1)

    // 初始化基本情况
    dp[1] = 1 // 1 没有拆分的可能，最大乘积是 1
    dp[2]=1
    for i := 3; i <= n; i++ {
        for j := 1; j < i; j++ {
            // dp[j]是拆分j后的最大乘积，i-j是剩下的部分
            // 需要考虑i-j本身是否可以拆分，取最大的结果
            dp[i] = max(dp[i], j*(i-j), dp[j]*(i-j))
        }
    }

    return dp[n]
}

来源链接：https://www.cnblogs.com/CharlseGo/p/18656274