Problem statement

https://binarysearch.com/problems/Stepping-Numbers/

Solution

Keep in dp states with (number of digits, last digit). In fact we can keep only 10 elements.

Complexity

It is O(10*n) for time and O(10) for space.

Code

class Solution:
    def solve(self, n):
        dp = [0] + [1] * 9
        M = 10**9 + 7
        for i in range(n - 1):
            dp2 = [0]*10
            for d in range(10):
                if d > 0: dp2[d] += dp[d - 1]
                if d < 9: dp2[d] += dp[d + 1]
                dp2[d] = dp2[d] % M
            dp = dp2
        
        return (sum(dp) + (n == 1)) % M