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

Arnab Chakraborty

更新於：2020年10月6日

203 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習