用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中，做以下步骤
  • 在列表最后插入(1 +所有元素的总和(a[i]*a[k-i]对于所有i在范围内(1，k)))模m
• 返回(a[n+1]-1)模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