Medium
有多少种可能性的这种题，我们可以使用动态规划的方式去思考。
推导过程：
0个数的情况：?
解释: 数字为0的可能性不确定，先放一下
1个数的情况：1
2个数的情况：
1. 左 1个数；右 0个数 可能性：1*1
2. 左 0个数；右 1个数 可能性：1*1
总的可能性：2
解释: 数字为一个的可能性之前已经求过了，可以直接拿来用
为了满足我们的通项数字为0的可能性设为1，没有元素，也是一种可能性
3个数的情况：
1. 左 2个数；右 0个数 可能性：2*1
2. 左 1个数；右 1个数 可能性：1*1
3. 左 0个数；右 2个数 可能性：1*2
总的可能性：5
可以在纸上先演算一下，推导到3个数的时候，我们应该就可以总结出推导过程了
dp[i] = sum(dp[i-1-j] * dp[j]) j=[0,i)
解释
通项的意思是，确定了一个数之后，左右两个树的左右可能性的和，就是当前个数的所有可能性
结果为卡塔兰数，感兴趣的小伙伴可以去了解一下
python3
def numTrees(self, n: int) -> int:
dp = [ 0 for _ in range(n+1) ]
dp[0] = 1
dp[1] = 1
for i in range(2,n+1):
for j in range(i):
dp[i] += dp[i-j-1] * dp[j]
return dp[-1]