मान लीजिए हमारे पास n चरणों वाली एक सीढ़ी है और एक अन्य संख्या k है। प्रारंभ में हम चरण 0 पर हैं, और हम एक बार में 1, 2 या 3 चरण चढ़ सकते हैं। लेकिन हम अधिकतम k बार ही 3 चरण चढ़ सकते हैं। अब हमें सीढ़ी चढ़ने के तरीकों की संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट है n = 5, k = 2, तो आउटपुट होगा 13, क्योंकि सीढ़ी चढ़ने के अलग-अलग तरीके हैं:
[1, 1, 1, 1, 1][2, 1, 1, 1][1, 2, 1, 1][1, 1, 2, 1][1, 1, 1, 2][1, 2, 2][2, 1, 2][2, 2, 1][1, 1, 3][1, 3, 1][3, 1, 1][2, 3][3, 2]
हल करने के चरण
- यदि
n0 के समान है, तो 1 लौटाएं। - यदि
n1 के समान है, तो 1 लौटाएं। k := min(k, n)memo:= आकार(n+1) x (k+1)का मैट्रिक्स।rको 0 सेkतक:memo[r][0] := 1,memo[r][1] := 1,memo[r][2] := 2
iको 3 सेnतक:memo[0][i] := memo[0][i-1] + memo[0][i-2]
jको 1 सेkतक:iको 3 सेnतक:count := i // 3- यदि
count <= j, तोmemo[j][i] := memo[j][i-1] + memo[j][i-2] + memo[j][i-3] - अन्यथा,
memo[j][i] := memo[j][i-1] + memo[j][i-2] + memo[j-1][i-3]
memo[k][n]लौटाएं।
उदाहरण
class Solution:
def solve(self, n, k):
if n == 0:
return 1
if n == 1:
return 1
k = min(k, n)
memo = [[0] * (n+1) for _ in range(k+1)]
for r in range(k+1):
memo[r][0] = 1
memo[r][1] = 1
memo[r][2] = 2
for i in range(3, n+1):
memo[0][i] = memo[0][i-1] + memo[0][i-2]
for j in range(1, k+1):
for i in range(3, n+1):
count = i // 3
if count <= j:
memo[j][i] = memo[j][i-1] + memo[j][i-2] + memo[j][i-3]
else:
memo[j][i] = memo[j][i-1] + memo[j][i-2] + memo[j-1][i-3]
return memo[k][n]
ob = Solution()
print(ob.solve(n=5, k=2))
इनपुट
5, 2
आउटपुट
13