Knight Dialer: Count Dialable Digit Sequences

Knight Dialer: Count Dialable Digit Sequences

A chess knight is placed on a standard telephone keypad:

1  2  3
4  5  6
7  8  9
*  0  #

The knight can only step on numeric digits (0 through 9). It cannot land on * or #. A legal move consists of moving two squares vertically and one horizontally, or two squares horizontally and one vertically (the standard L-shape move in chess).

Given an integer n, return the total number of distinct numeric sequences of length n you can dial. You may start the knight on any numeric digit. Because the answer may be very large, return it modulo 10^9 + 7 (1000000007).

Function Signature

def knight_dialer(n: int) -> int:
    pass

Constraints

• 1 <= n <= 5000

Examples

Example 1:

Input: n = 1
Output: 10
Explanation: With length 1, starting on any of the 10 digits produces a valid 1-digit sequence: [0], [1], ..., [9].

Example 2:

Input: n = 2
Output: 20
Explanation: 
Starting on 0 gives: 04, 06 (2)
Starting on 1 gives: 16, 18 (2)
Starting on 2 gives: 27, 29 (2)
Starting on 3 gives: 34, 38 (2)
Starting on 4 gives: 40, 43, 49 (3)
Starting on 5 gives: none (0)
Starting on 6 gives: 60, 61, 67 (3)
Starting on 7 gives: 72, 76 (2)
Starting on 8 gives: 81, 83 (2)
Starting on 9 gives: 92, 94 (2)
Total = 2 + 2 + 2 + 2 + 3 + 0 + 3 + 2 + 2 + 2 = 20.

Example 3:

Input: n = 3
Output: 46

Edge Cases to Consider

• n = 1: Digit 5 can be dialed once since no moves are required, but for n > 1, sequences starting or landing on 5 are impossible because 5 has no legal knight moves.
• Large n: Ensure transitions and running sums apply the modulo at each step to prevent overflow or unnecessary memory overhead.