Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में सीढ़ियां चढ़ने के तरीकों की संख्या खोजें (अधिकतम चरण अधिकतम 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 := 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
  1. Python में मैट्रिक्स के खाली सेल चुनने के कितने तरीके हैं, इसकी जांच करने का प्रोग्राम Python में मैट्रिक्स के खाली सेल चुनने के कितने तरीके हैं, इसकी जांच करने का प्रोग्राम

    मान लीजिए हमारे पास एक N x N बाइनरी मैट्रिक्स है जहां 0 खाली सेल के लिए है और 1 ब्लॉक्ड सेल है, हमें N खाली सेल चुनने के तरीकों की संख्या ढूंढनी है ताकि हर पंक्ति और हर कॉलम में कम से कम एक चुना हुआ सेल हो। यदि उत्तर बहुत बड़ा है तो परिणाम mod 10^9 + 7 लौटाएंइसलिए, यदि इनपुट इस तरह है000000010तो आउट

  1. पायथन में हम कितना कुल वर्षा जल पकड़ सकते हैं यह खोजने का प्रोग्राम पायथन में हम कितना कुल वर्षा जल पकड़ सकते हैं यह खोजने का प्रोग्राम

    मान लीजिए हमारे पास n गैर-ऋणात्मक पूर्णांकों की एक सरणी है। ये एक ऊंचाई को दर्शा रहे हैं जहां प्रत्येक बार की चौड़ाई 1 है, हमें गणना करनी है कि बारिश के बाद यह कितना पानी पकड़ सकता है। तो मानचित्र इस तरह होगा −यहां हम 8 नीले बॉक्स देख सकते हैं, इसलिए आउटपुट 8 होगा।इसे हल करने के लिए, हम इन चरण

  1. पायथन में ट्री को दो ट्री में विभाजित करने के तरीकों की गिनती का प्रोग्राम पायथन में ट्री को दो ट्री में विभाजित करने के तरीकों की गिनती का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें 0, 1 और 2 मान हैं। रूट में कम से कम एक 0 नोड और एक 1 नोड है। अब मान लीजिए एक ऑपरेशन है जहां हम ट्री में एक किनारा हटाते हैं और ट्री दो अलग-अलग ट्री बन जाता है। हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम एक किनारा हटा सकते हैं जैसे कि दोनों ट्री में से को