题目力扣链接
代码随想录链接
动态规划找到子状态之间的关系很重要！
-
dp数组定义：1到i为节点组成的二叉搜索树的个数为dp[i]
-
初始化：初始化dp[0]为零，空树为一种情况
-
递推公式：（注意是以j遍历哪个为头节点，再将所有情况累加）dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
class Solution:def numTrees(self, n: int) -> int:dp = [0] * (n+1)dp[0] = 1 # 当n为0时，只有一种情况，即空树，所以dp[0] = 1for i in range(1, n+1):for j in range(1, i+1): # 对于每个数字i，计算以i为根节点的二叉搜索树的数量dp[i] += dp[j-1] * dp[i-j] # 乘法两边分别是左子树和右子树的数量return dp[n]