โปรแกรมนับจำนวน stepping number ที่มี n หลักใน Python

Stepping number คือตัวเลขที่หลักติดกันต่างกัน 1 (เช่น 123 เป็น, 124 ไม่เป็น) หาจำนวน stepping number n หลัก mod 10^9+7

เช่น n=2 ให้ 17 ตัว: [12,23,34,45,56,67,78,89,98,87,76,65,54,43,32,21,10]

ขั้นตอนการแก้ปัญหา

• dp[d] := จำนวน stepping number ที่ลงท้ายด้วย d
• เริ่ม dp = [1]*10 (n=1)
• วน n-1 รอบ: ndp[0]=dp[1], ndp[9]=dp[8], ndp[i]=dp[i-1]+dp[i+1]
• คืนค่า sum(dp[1:]) % MOD

ตัวอย่างโค้ด

class Solution:
    def solve(self, n):
        MOD = 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]) % MOD
            ndp[9] = dp[8]
            dp = ndp
        return sum(dp[1:]) % MOD

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

อินพุต

3

เอาต์พุต

32