Chương trình đếm số bước nhảy (stepping numbers) n chữ số bằng Python

Số bước nhảy (stepping number) là số mà hiệu tuyệt đối giữa mọi hai chữ số liền kề bằng 1. Đếm số stepping number có n chữ số (mod 10^9+7).

Ví dụ: n=2 → 17 số (10,12,21,23,...,98).

Giải thuật

• Quy hoạch động: dp[d] = số stepping number kết thúc bằng chữ số d.
• Khởi tạo dp = [1]*10 cho n=1.
• Lặp n-1 lần: ndp[0]=dp[1], ndp[i]=dp[i-1]+dp[i+1] (1≤i≤8), ndp[9]=dp[8].
• Kết quả: tổng dp[1:] modulo 10^9+7.

Ví dụ minh họa

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

Đầu vào

3

Đầu ra

32