0096：不同的二叉搜索树（★）

1
2
3
4
5
6

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [1]*(n+1)
        for i in range(1,n+1):
            dp[i] = sum(dp[j-1]*dp[i-j] for j in range(1,i+1))
        return dp[-1]

1
2
3

class Solution:
    def numTrees(self, n: int) -> int:
        return comb(2*n,n)//(n+1)