模版题-动态规划-不同的二叉搜索树 ( 并不确定就是动态规划 但是在推导过程中 确定需要记录的信息 确定是动态规划 )
- 版权声明：本站原创文章，于2026-05-11，由 管理员 发表。
- 转载请注明： 模版题-动态规划-不同的二叉搜索树 ( 并不确定就是动态规划 但是在推导过程中 确定需要记录的信息 确定是动态规划 ) | CodeGarden
**并不确定就是动态规划 但是在推导过程中 确定需要记录的信息 确定是动态规划**
```python
class Solution:
# 一个整数n，求恰由n个节点组成且节点值从 1到n 互不相同的二叉搜索树有多少种？
# 返回满足题意的二叉搜索树的种数。
def numTrees(self, n: int) -> int:
# n = 1: 1种
# n = 2: 1为根 2为根, 剩余一个节点组成的子树挂载: 2种
# n = 3: 1为根 2为根 3为根, 剩余两个节点组成的子树挂载
# 1为根 剩余节点2和3 只能挂在1右边, 2个节点2种组成, 故2种
# 2为根 剩余节点1和3 只能一个挂在左边 一个挂在右边, 1个节点1种组成, 故1种
# 3为根 剩余节点1和2 只能挂在3左边, 2个节点2种组成, 故2种
# 合计5种。
# ----
# 如果上述过程是自己模拟的，到这里其实已经可以发现n个节点能够形成几种不同的二叉搜索树:
# 分别以1, 2, 3, ..., n 为根节点，记为x
# 确定根节点x左侧和右侧有几个节点，分别能够组成几种二叉搜索树
# 合计即为总种数。 —— 所以dp需要记录什么也很清楚了
# ----
# dp( i )表示i个节点能组成的互不相同的二叉搜索树种数
dp = [ 0 for _ in range( n + 1 ) ]
dp[ 0 ] = 0
dp[ 1 ] = 1
for i in range( 2, n + 1 ):
# 分别以x为根节点
for x in range( 1, i + 1 ):
# x左边有 x - 1个节点
# x右边有 i - x个节点
l = dp[ x - 1 ]
r = dp[ i - x ]
if x - 1 == 0: dp[ i ] += r
elif i - x == 0: dp[ i ] += l
else: dp[ i ] += ( l * r )
return dp[ n ]
```