解题思路
动态规划
对于元素数量是i的二叉搜索树
左子树的元素数量j，右子树的元素数量i-j-1，根1
total == i
方案树为j从0到i-1的所有情况下的组合，每一种的数量为dp[j] * dp[i-j-1]
96. 不同的二叉搜索树
代码
class Solution(object):
def numTrees(self, n):
dp = [0 for _ in range(n+1)]
dp[0] = 1
for i in range(1, n+1):
for j in range(i):
# 左子树的元素数量j，右子树的元素数量i-j-1，根1
#total == i
dp[i] += dp[j] * dp[i-j-1]
# 当i是n时，就是答案
return dp[n]
效果图
