leetcode 第95题 python

leetcode第95题是关于二叉搜索树的问题。
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种不同的结构。
为了解决这个问题，我们可以使用动态规划的方法。我们可以将问题分解成小问题，并通过已知的结果来计算出解。
首先，我们注意到当节点数为0时，二叉搜索树的数量为1，当节点数为1时，二叉搜索树的数量也为1。
对于节点数大于1的情况，我们对每个节点i作为根节点进行考虑。将1到i-1作为左子树，i+1到n作为右子树。
我们可以得到左子树的结构数、右子树的结构数，然后将左子树的结构数乘以右子树的结构数，即可得到以节点i为根节点的二叉搜索树总数。
然后，我们将所有以节点i为根节点的二叉搜索树的总数相加，即可得到所有可能的结构。
所以我们可以使用一个数组dp，dp[i]表示i个节点组成的二叉搜索树的总数。
根据以上思路，我们可以写出以下代码实现：

def numTrees(n):
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]

return dp[n]

这样，当输入为n时，函数会返回以1到n为节点的二叉搜索树的总数。