สมมติว่าเรามีตัวเลข n ถ้าเรามีตัวเลขเช่น [1,2,...,n] เราต้องนับจำนวน BST ที่เป็นไปได้ที่สามารถสร้างได้โดยใช้ค่า n เหล่านี้ หากคำตอบมีขนาดใหญ่เกินไป ให้แก้ไขผลลัพธ์ด้วย 10^9+7
ดังนั้น หากอินพุตเท่ากับ n =3 เอาต์พุตจะเป็น 14
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้
- a :=รายการที่มีค่า [0, 1]
- ม :=10^9+7
- max_n :=1,000
- สำหรับ k ในช่วง 2 ถึง max_n + 1 ทำ
- แทรก (1 + ผลรวมขององค์ประกอบทั้งหมดของรายการ (a[i] * a[k - i] สำหรับ i ทั้งหมดในช่วง (1, k))) mod m ที่ส่วนท้ายของ a
- ผลตอบแทน (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
