मान लीजिए हमारे पास एक संख्या n है। हमें पहले n फाइबोनैचि पदों का योग ज्ञात करना है (n पदों तक फाइबोनैचि अनुक्रम)। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^8 + 7 के मॉड्यूलो में लौटाएं।
उदाहरण के लिए, यदि इनपुट n = 8 है, तो आउटपुट 33 होगा क्योंकि पहले कुछ फाइबोनैचि पद हैं: 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33।
समाधान दृष्टिकोण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- m := 10^8 + 7
- memo := एक नया मैप (डिक्शनरी)
- एक फंक्शन solve() परिभाषित करें जो n और m लेता है
- यदि n memo में है, तो memo[n] लौटाएं
- memo[n] := n जब n < 2 अन्यथा (solve(n-1, m) + solve(n-2, m)) mod m
- memo[n] लौटाएं
- मुख्य विधि से memo के मानों की सूची प्राप्त करें और उनका योग लें
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
m = 10**8 + 7
memo = {}
def solve(n, m):
if n in memo:
return memo[n]
memo[n] = n if n < 2 else (solve(n-1, m) + solve(n-2, m)) % m
return memo[n]
n = 8
solve(n, m)
print(sum(list(memo.values())[:n]))इनपुट
8
आउटपुट
33
