मान लीजिए हमारे पास n चरणों वाली एक सीढ़ी है, और हम एक बार में 1 या 2 चरण चढ़ सकते हैं। हमें एक फ़ंक्शन परिभाषित करना है जो सीढ़ी चढ़ने के अद्वितीय तरीकों की संख्या लौटाता है।
चरणों का क्रम नहीं बदला जाना चाहिए, इसलिए चरणों का प्रत्येक अलग क्रम एक तरीका गिना जाता है। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9 + 7 से मोड करें।
उदाहरण के लिए, यदि इनपुट है n = 5, तो आउटपुट होगा 8, क्योंकि 8 अद्वितीय तरीके हैं:
1, 1, 1, 1, 12, 1, 1, 11, 2, 1, 11, 1, 2, 11, 1, 1, 21, 2, 22, 1, 22, 2, 1
हल करने के चरण
dp:= आकारn+1का सरणी, 0 से भरा हुआ।dp[1] := 1iको 2 सेn+1तक:dp[i] := dp[i-1] + dp[i-2]
dpके अंतिम तत्व कोmसे मोड करके लौटाएं।
उदाहरण
m = (10**9) + 7
class Solution:
def solve(self, n):
dp = [0 for _ in range(n+2)]
dp[1] = 1
for i in range(2, n+2):
dp[i] = dp[i-1] + dp[i-2]
return dp[-1] % m
ob = Solution()
print(ob.solve(5))
इनपुट
5
आउटपुट
8