作者介绍: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))优势结构清晰、易于实现避免重复计算、提高效率计算最快、不需要额外空间劣势计算时间较长空间复杂度较高,较复杂需要理解卡塔兰数背后的数学原理

应用示例

这些方法可以用于算法设计与数据结构教学中,展示不同的动态规划技术和数学应用。它们也适用于任何需要预测或计算不同结构可能性的领域,如计算生物学、化学结构分析等领域。

相关文章

评论可见,请评论后查看内容,谢谢!!!
 您阅读本篇文章共花了: