题解 | 有多少个不同的二叉搜索树 Python3

import sys



# 11:28

# 假设之前的1～i个数，i个节点，有d[i]个不同的构成方法
# 新加i+1, d[i+1] = ?
# 1. 因为 i+1 >i, 所以可以直接作为根节点，i的左右搜索树作为i的左子节点
# 2. 因为 i+1 > i, 所以可以直接加在 i的所有搜索树的最右边作为叶子节点
# 3. 也可以在右边的每一层作为某一层有子树的根节点，其他的点则调整为左子树，即其可在右子树的每一个位置
# 对于第3点，需要知道右节点有多少个节点，因此需考虑根节点的值，
# 重新考虑如何计算dp[i+1]
# 有i个节点的时候，当以j为根节点，左边有1～j-1个点，左子树的搜索二叉树个数为dp[j-1]，右子树的节点数为j+1~i, 即dp[i-j]
# dp[i] = sum(dp[j-1]*dp[i-j] for j in range(1,i))
n = int(input())

dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2,n+1):
    for j in range(1,i+1):
        dp[i] += dp[j-1] * dp[i-j]

print(dp[-1])