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 次浏览

启动你的职业生涯

通过完成课程获得认证

开始学习
广告