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]

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

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

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

उदाहरण

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))