পাইথনে n অঙ্কের স্টেপিং সংখ্যা গণনা করার প্রোগ্রাম

একটি সংখ্যা n দেওয়া আছে। n-অঙ্কের স্টেপিং সংখ্যা কতগুলো আছে তা বের করুন। স্টেপিং সংখ্যা হলো যের সন্নিহিত অঙ্কগুলোর পার্থক্য ১। বড় হলে ১০^৯+৭ দিয়ে মডুলো।

উদাহরণ: n=2 → আউটপুট ১৭।

সমাধানের ধাপগুলো:

• m = 10**9+7।
• n==0 → ০, n==1 → ১০।
• DP অ্যারে দিয়ে প্রতিটি ডিজিটের জন্য গণনা করুন।
• শেষে sum(dp[1:]) % 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))

ইনপুট

3

আউটপুট

32