পাইথনে n স্বতন্ত্র নোড ব্যবহার করে সম্ভাব্য BST গুলির সংখ্যা খুঁজে বের করার প্রোগ্রাম তৈরি করা যেতে পারে

ধরুন আমাদের একটি সংখ্যা n আছে। আমাদের যদি [1,2,...,n] এর মতো সংখ্যা থাকে তবে আমাদের এই n মানগুলি ব্যবহার করে সম্ভাব্য BST গুলির সংখ্যা গণনা করতে হবে। যদি উত্তরটি খুব বড় হয়, তাহলে ফলাফলটি 10^9+7 দ্বারা পরিবর্তন করুন।

সুতরাং, যদি ইনপুট n =3 এর মত হয়, তাহলে আউটপুট হবে 14,

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব

a :=একটি তালিকা [0, 1]
m :=10^9+7
max_n :=1000
2 থেকে max_n + 1 রেঞ্জের k-এর জন্য, করুন
- (1 + তালিকার সমস্ত উপাদানের যোগফল (a[i] * a[k - i] পরিসরের সমস্ত i (1, k))) a এর শেষে 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))