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

假设我们有一个数字n，我们需要找到使用[0, n)范围内的数字可以生成的唯一BST的数量。如果答案非常大，则对10^9+7取模。

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

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

  • 分子 := 1
  • 分母 := n + 1
  • 对于 i 从1到n，执行：
    • 分子 := 分子 * (n + i)
    • 分子 := 分子 mod m
    • 分母 := 分母 * i
    • 分母 := 分母 mod m
  • 分子 := 分子 * (分母^(m-2)) mod m
  • 返回 分子 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))

输入

4

输出

14

更新于：2020年10月6日

203 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告