用 Python 编写程序，计算可以用 0 到 n 个值形成的唯一二叉搜索树的数量

pythonserver side programmingprogramming更新于 2026/1/10 15:40:17

假设我们有一个数字 n，我们必须找到可以用 [0, n) 中的数字生成的唯一 BST 的数量。如果答案非常大，则将结果取 10^9+7 的模

因此，如果输入为 n = 3，则输出将为 5

为了解决这个问题，我们将遵循以下步骤 −

numer := 1
denom := n + 1
对于范围从 1 到 n 的 i，执行
- numer := numer * n + i
- numer := numer mod m
- denom := denom * i
- denom := denom mod m
numer := numer * (denom^(m-2)) mod m
返回 numer mod m

让我们看看下面的实现以便更好地理解 −

示例

class Solution:
   def solve(self, n):
      m = 10 ** 9 + 7
      numer = 1
      denom = n + 1
      for i in range(1, n + 1):
         numer *= n + i
         numer %= m
         denom *= i
         denom %= m
         numer *= pow(denom, m-2, m)
      return numer % m
ob = Solution()
print(ob.solve(4))