96.不同的二叉搜索树
1、关键点找出状态转移方程
class Solution:
def numTrees(self, n: int) -> int:
# 创建 dp 数组， dp[i] 代表节点数为 i 的二叉搜索树数量
dp = [0]*(n+1)
# 初始化数组
dp[0] = 1
# 遍历每个元素作为根节点
for i in range(n+1):
for j in range(1, i+1):
# 状态转移方程。左子树数量*右子数数量
dp[i] += dp[j-1]*dp[i-j]
return dp[n]