मान लीजिए हमारे पास एक संख्या 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) में)) 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
