作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。 会一些的技术：数据分析、算法、SQL、大数据相关、python 欢迎加入社区：码上找工作 作者专栏每日更新： LeetCode解锁1000题: 打怪升级之旅 python数据分析可视化：企业实战案例 python源码解读 程序员必备的数学知识与应用 备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个整数 n，求以 1 到 n 为节点组成的二叉搜索树 (BST) 有多少种不同的形状。
输入格式
n：整数，表示节点的数目。
输出格式
返回不同的 BST 的数目。
示例
示例 1
输入: n = 3
输出: 5
解释:
给定 n = 3, 有五种不同形状的 BST:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
方法一：动态规划
解题步骤
定义状态：dp[i] 表示由 i 个节点能构成的不同 BST 的数目。状态转移：dp[i] 由所有可能的左右子树的组合数之和决定。即 dp[i] = ∑(dp[j-1] * dp[i-j])，其中 j 表示根节点的位置。
完整的规范代码
def numTrees(n):
"""
使用动态规划计算不同的二叉搜索树的数量
:param n: int, 节点的数目
:return: int, 不同的 BST 数量
"""
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1
for i in range(2, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[n]
# 示例调用
print(numTrees(3)) # 输出: 5
算法分析
时间复杂度：(O(n^2))，由于双层循环的存在。空间复杂度：(O(n))，用于存储中间结果的数组。
算法图解
为了提供一个更直观的视觉展示来理解问题 96 “不同的二叉搜索树” 使用动态规划方法的计算过程，我们可以尝试通过一个更细节的 ASCII 图形来表达 dp 数组的更新流程，这会帮助我们直观地看到每一步的计算和累加过程。
假设我们计算 n = 4 时的情况，我们详细列出每一步的计算，展示根节点选择不同的情况如何贡献到 dp 数组的计算中。
ASCII 表的直观表示
这里是一个逐步展开的表格，用于计算不同的二叉搜索树数量，其中 | 表示不同的根节点选择对应的贡献。
dp[0] = 1 (空树)
dp[1] = 1 (单节点树)
Calculating dp[2]:
Root 1: dp[0] * dp[1] = 1 * 1 = 1 | 1
Root 2: dp[1] * dp[0] = 1 * 1 = 1 | 1
dp[2] = 1 + 1 = 2
Calculating dp[3]:
Root 1: dp[0] * dp[2] = 1 * 2 = 2 | 2
Root 2: dp[1] * dp[1] = 1 * 1 = 1 | 1
Root 3: dp[2] * dp[0] = 2 * 1 = 2 | 2
dp[3] = 2 + 1 + 2 = 5
Calculating dp[4]:
Root 1: dp[0] * dp[3] = 1 * 5 = 5 | 5
Root 2: dp[1] * dp[2] = 1 * 2 = 2 | 2
Root 3: dp[2] * dp[1] = 2 * 1 = 2 | 2
Root 4: dp[3] * dp[0] = 5 * 1 = 5 | 5
dp[4] = 5 + 2 + 2 + 5 = 14
可视化解释
每一行表示计算一个 dp[i] 的过程。| 之后的数字表示该根节点下左右子树组合的贡献。每个 Root x: 开头的部分表示选择 x 作为根节点时，左右子树组成部分的贡献。
这种方式的展示将每个步骤拆分开来，明确每个选择的贡献如何累加到最终结果中，从而帮助读者更好地理解动态规划表是如何一步步构建起来的，特别是如何通过结合前面计算的结果来解决当前问题的。希望这种方法能够更直观地展示动态规划的计算过程。
方法二：递归（带记忆化）
解题步骤
递归定义：利用递归直接根据 dp 的定义进行计算，对于每个 i 计算 1 到 i 的根节点所能形成的 BST 数量。记忆化：使用哈希表存储已计算的结果，避免重复计算。
完整的规范代码
def numTrees(n):
memo = {}
def countTrees(n):
if n in memo:
return memo[n]
if n <= 1:
return 1
total = 0
for i in range(1, n + 1):
left = countTrees(i - 1)
right = countTrees(n - i)
total += left * right
memo[n] = total
return total
return countTrees(n)
# 示例调用
print(numTrees(3)) # 输出: 5
算法分析
时间复杂度：(O(n^2))，尽管有递归调用，但由于记忆化的存在，每个子问题只解决一次。空间复杂度：(O(n))，用于存储记忆化结果的哈希表。
方法三：数学公式 - 卡塔兰数
解题步骤
完整的规范代码
def numTrees(n):
"""
使用卡塔兰数公式计算不同的二叉搜索树的数量
:param n: int, 节点的数目
:return: int, 不同的 BST 数量
"""
import math
return math.comb(2 * n, n) // (n + 1)
# 示例调用
print(numTrees(3)) # 输出: 5
算法分析
时间复杂度：(O(n))，主要消耗在计算组合数上。空间复杂度：(O(1))，不需要额外的存储空间。
不同算法的优劣势对比
特征方法一：动态规划方法二：递归（带记忆化）方法三：卡塔兰数时间复杂度(O(n^2))(O(n^2))(O(n))空间复杂度(O(n))(O(n))(O(1))优势结构清晰、易于实现避免重复计算、提高效率计算最快、不需要额外空间劣势计算时间较长空间复杂度较高，较复杂需要理解卡塔兰数背后的数学原理
应用示例
这些方法可以用于算法设计与数据结构教学中，展示不同的动态规划技术和数学应用。它们也适用于任何需要预测或计算不同结构可能性的领域，如计算生物学、化学结构分析等领域。
相关文章
您阅读本篇文章共花了： 大家都在找：
算法：算法的描述方法有哪些
leetcode：leetcode是什么
python：python下载
动态规划：动态规划01背包问题
面试：面试必问10大问题回答
发表评论