Python程式：求解使用n個不同節點可以生成的BST數量

假設我們有一個數字n。如果我們有像[1,2,...,n]這樣的數字，我們必須計算使用這些n個值可以形成的BST的數量。如果答案太大，則對結果取模10^9+7。

因此，如果輸入是n = 3，則輸出將是14。

為了解決這個問題，我們將遵循以下步驟：

  • a := 一個值為[0, 1]的列表
  • m := 10^9+7
  • max_n := 1000
  • 對於k從2到max_n + 1，執行：
    • 在a的末尾插入 (1 + 所有元素之和 (a[i] * a[k - i]，對於所有i從1到k-1)) mod m
  • 返回 (a[n + 1] - 1) mod m

示例

讓我們看看下面的實現，以便更好地理解：

def solve(n):
   a = [0, 1]
   m = 10**9+7
   max_n = 1000

   for k in range(2, max_n + 2):
      a.append((1 + sum(a[i] * a[k - i] for i in range(1, k))) % m)
   return ((a[n + 1] - 1) % m)

n = 3
print(solve(n))

輸入

3

輸出

14

更新於：2021年10月23日

72 次瀏覽

啟動你的職業生涯

透過完成課程獲得認證

開始學習
廣告