पायथन में सीढ़ियाँ चढ़ने के कितने तरीके हैं (अधिकतम k बार में अधिकतम कदम) खोजने के लिए कार्यक्रम

मान लीजिए कि हमारे पास 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]

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

यदि n, 0 के समान है, तो
- वापसी 1
यदि n 1 के समान है, तो
- वापसी 1
k:=न्यूनतम k, n
ज्ञापन:=आकार का एक मैट्रिक्स (n+1) x (k+1)
r के लिए 0 से k की सीमा में, करें
- मेमो[आर, 0]:=1, मेमो[आर, 1]:=1, मेमो[आर, 2]:=2
3 से n की श्रेणी में i के लिए, करें
- ज्ञापन[0, i]:=ज्ञापन[0, i-1] + ज्ञापन[0, i-2]
जे के लिए 1 से के रेंज में, करें
- 3 से n की श्रेणी में i के लिए, करें
  - गिनती :=i/3 का भागफल
  - अगर गिनती <=j, तो
    - मेमो[j, i]:=मेमो[j, i-1] + मेमो[j, i-2] + मेमो[j, i-3]
  - अन्यथा,
    - मेमो[j, i]:=मेमो[j, i-1] + मेमो[j, i-2] + मेमो[j-1, i-3]
रिटर्न मेमो[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