Medium

Knight Dialer

LAB

Return how many distinct phone numbers of length n can be dialed by moving a chess knight on a keypad, modulo 1000000007.

EXAMPLES

Example 1

Input
{
  "n": 2
}

Output
20

FUNCTION SHAPE

n: int→int

SOLUTION NOTE

Precompute valid knight moves from each digit. DP counts paths of length n starting from each digit.

Reveal reference solution +

pythonREFERENCE

def knightDialer(self, n: int) -> int:
    MOD = 10 ** 9 + 7
    # Knight moves from each digit
    moves = {
        0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8],
        4: [0, 3, 9], 5: [], 6: [0, 1, 7], 7: [2, 6],
        8: [1, 3], 9: [2, 4]
    }

    @cache
    def dp(digit, remaining):
        if remaining == 0:
            return 1
        return sum(dp(next_d, remaining - 1) for next_d in moves[digit]) % MOD

    return sum(dp(d, n - 1) for d in range(10)) % MOD

TimeO(n)

SpaceO(n)

Open on LeetCode ↗