935 Knight Dialer

link Knight Dialer

Thought

Since it ask how many distinct numbers could be generated, DP jumps to my mind immediately. Firstly, the relation is, if knight stop at number 6, it has to come from 1, 7, or 0. So I keep a DP array, DP[j][i] stands for how many unique numbers it could generate if knight jumps j steps and stops at i position. Then, I find actually DP[j+i] only depends on DP[j] level, so I could optimize 2D DP array into 1D array.

One tircky part to notice: DP[1][5] is 1, other than that, DP[j][5] is 0 iif j > 1.

Code

class Solution:
    def knightDialer(self, N):
        """
        :type N: int
        :rtype: int
        """
        MOD = 10**9 + 7
        DP = [1] * 10 #init state
        for hops in range(N-1):
            Q = [0] * 10
            Q[0] = (DP[4] + DP[6]) % MOD
            Q[1] = (DP[8] + DP[6]) % MOD
            Q[2] = (DP[7] + DP[9]) % MOD
            Q[3] = (DP[4] + DP[8]) % MOD
            Q[4] = (DP[3] + DP[0] +DP[9]) % MOD
            Q[6] = (DP[1] +DP[7] + DP[0]) % MOD
            Q[7] = (DP[2] + DP[6]) % MOD
            Q[8] = (DP[1] + DP[3]) % MOD
            Q[9] = (DP[4] + DP[2]) % MOD
            DP = Q
        return sum(DP) % MOD

Runtime

Time: O(n) Space: O(n)