Problem statement

https://leetcode.com/problems/knight-dialer/

Solution

We can use dp with 10 states, where dp[step][i] is number of ways to finish at cell i. Notice that in fact we only need to keep one row at at time.

Complexity

It is O(n * m), where m = 20 here is number of possible moves of knight.

Code

class Solution:
    def knightDialer(self, n):
        d = {0:(4,6), 1:(6,8), 2:(7,9), 3:(4,8), 4:(3,9,0), 5:(), 6:(1,7,0), 7:(2,6), 8:(1,3), 9:(2,4)}
        M = 10**9 + 7
        dp = [1]*10
        for i in range(n-1):
            dp2 = [0]*10
            for i in range(10):
                for prev in d[i]:
                    dp2[i] += dp[prev]
            dp = [i%M for i in dp2]
            
        return sum(dp) % M

Remark

There is also matrix power solution with complexity O(10^3 * log n).