「力扣」第 96 题：不同的二叉搜索树
给定一个整数
n，求以1 ... n为节点组成的二叉搜索树有多少种？示例：
输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
方法一：动态规划
这里 j 表示左子树的元素个数，最小是 0 ，最大是 i - 1。
注意：这里 $0$ 个结点构成的子树的个数为 $1$，这个值是我们需要的，因此需要多开 $1$ 个空间。
Java 代码：
public class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
// 想清楚这个值很关键
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// 这里 j 表示左子树的元素个数，最小是 0 ，最大是 i - 1
// 左边子树 + 右边子树 = i - 1
// i - j - 1 表示的是右边子树元素个数
for (int j = 0; j < i; j++) {
// 使用 * 是因为乘法计数原理
dp[i] += dp[j] * dp[i - j - 1];
}
}
return dp[n];
}
}Python 代码：
class Solution:
def numTrees(self, n: int) -> int:
if n == 0 or n == 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(i):
dp[i] += dp[j] * dp[i - j - 1]
return dp[n]（另一种写法）
Python 代码：
class Solution:
def numTrees(self, n: int) -> int:
# 因为需要 0 ，所以多开 1 个空间
dp = [0 for _ in range(n + 1)]
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(i):
dp[i] += dp[j] * dp[i - j - 1]
return dp[n]方法二：动态规划的优化
Java 代码：
public class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
// 乘法因子的单位是 1
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < n + 1; i++) {
for (int j = 0; j < i / 2; j++) {
dp[i] += 2 * (dp[j] * dp[i - j - 1]);
}
if ((i & 1) == 1) {
dp[i] += dp[i / 2] * dp[i / 2];
}
}
return dp[n];
}
}Python 代码：
class Solution:
def numTrees(self, n: int) -> int:
# 因为需要 0 ，所以多开 1 个空间
dp = [0 for _ in range(n + 1)]
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(i // 2):
dp[i] += 2 * (dp[j] * dp[i - j - 1])
if i & 1:
# 如果是奇数
dp[i] += dp[i // 2] * dp[i // 2]
return dp[n]（本节完）
