पायथन में अलग-अलग नोड्स का उपयोग करके संभावित बीएसटी की संख्या का पता लगाने के लिए कार्यक्रम तैयार किया जा सकता है

मान लीजिए कि हमारे पास एक संख्या n है। यदि हमारे पास [1,2,...,n] जैसी संख्याएँ हैं, तो हमें इन n मानों का उपयोग करके संभावित BST की संख्या को गिनना होगा। अगर उत्तर बहुत बड़ा है, तो परिणाम को 10^9+7 से संशोधित करें।

इसलिए, यदि इनपुट n =3 जैसा है, तो आउटपुट 14 होगा,

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे

• a :=मानों वाली एक सूची [0, 1]
• म :=10^9+7
• अधिकतम_एन:=1000
• k के लिए 2 से लेकर max_n + 1 तक, करें
  • सम्मिलित करें (सूची के सभी तत्वों का 1 + योग (a[i] * a[k - i] सभी के लिए i रेंज में(1, k))) mod m a के अंत में
• वापसी (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