पायथन में n अंकों की स्टेपिंग संख्याओं की संख्या गिनने का कार्यक्रम

मान लीजिए कि हमारे पास एक संख्या n है, तो हमें n अंकों की चरणबद्ध संख्याओं की संख्या ज्ञात करनी है। जैसा कि हम जानते हैं कि एक संख्या को स्टेपिंग नंबर कहा जाता है, जब सभी आसन्न अंकों में 1 का पूर्ण अंतर होता है। इसलिए यदि कोई संख्या 123 है, तो यह स्टेपिंग नंबर है, लेकिन 124 नहीं है। अगर उत्तर बहुत बड़ा है तो परिणाम मोड 10^9 + 7 लौटाएं।

इसलिए, यदि इनपुट n =2 जैसा है, तो आउटपुट 17 होगा, क्योंकि स्टेपिंग नंबर हैं [12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21, 10]

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

• म :=10^9 + 7
• यदि n, 0 के समान है, तो
  • वापसी 0
• यदि n 1 के समान है, तो
  • वापस 10
• dp :=मान 1 से भरे आकार 10 की एक सूची
• पुनरावृति n - 1 बार, करें
  • ndp :=मान 0 से भरे 10 आकार की एक सूची
  • ndp[0] :=dp[1]
  • 1 से 8 के बीच के लिए, करें
    • ndp[i] :=dp[i - 1] + dp[i + 1]
  • एनडीपी[9] :=डीपी[8]
  • डीपी:=एनडीपी
• रिटर्न (डीपी के सभी नंबरों का योग [इंडेक्स 1 से अंत तक]) मॉड एम

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution:
   def solve(self, n):
      m = (10 ** 9 + 7)
      if n == 0:
         return 0
      if n == 1:
         return 10
      dp = [1] * 10
      for _ in range(n - 1):
         ndp = [0] * 10
         ndp[0] = dp[1]
         for i in range(1, 9):
            ndp[i] = dp[i - 1] + dp[i + 1]
         ndp[9] = dp[8]
         dp = ndp
      return sum(dp[1:]) % m

ob = Solution()
n = 3
print(ob.solve(n))

इनपुट

3

आउटपुट

32