> ## Content Index
> Fetch the complete content index at: https://andybase.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 935 Knight Dialer
- URL: https://andybase.com/935-knight-dialer/
- Published: 2018-11-08T21:37:50.000Z
- Updated: 2018-11-08T21:37:50.000Z
- Author: andy
- Tags: leetcode, contest, #Migrated-1784083136856, #wp, #wp-post, #Import 2026-07-15 02:38

link [Knight Dialer](https://leetcode.com/problems/knight-dialer/?ref=andybase.com)

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