NeetCode #693LC-935Medium1-D Dynamic Programming
← Back to All Problems#693 · #935 · Knight Dialer(骑士拨号器)
📌 Problem Statement & Constraints
A chess knight dials phone numbers on a keypad shaped like a
3 x 4 grid holding the digits 0-9 (the bottom-left and bottom-right cells do not exist). Count how many distinct phone numbers of length n the knight can dial using n - 1 valid knight moves, modulo 10^9 + 7. Constraints: 1 <= n <= 5000.💡 Core Algorithmic Approaches
- Model the keypad as a graph: each digit is a node and a knight move is an edge.
- Let
dp[v]be the number of distinct length-inumbers ending on digitv; thendp_next[u] = sum(dp[v])over everyvthat can jump tou. - The move graph is fixed, so each step costs a constant amount of work across the ten digits.
- A length-1 number can end on any digit, so every
dp[v]starts at 1; the answer issum(dp)afternsteps.
💻 Benchmark Python3 Implementation
class Solution:
def knightDialer(self, n: int) -> int:
MOD = 10 ** 9 + 7
# moves[v] = digits reachable from v in one knight move
moves = [
[4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9],
[], [0, 1, 7], [2, 6], [1, 3], [2, 4],
]
dp = [1] * 10 # length-1 numbers end anywhere
for _ in range(n - 1):
ndp = [0] * 10
for v in range(10):
for u in moves[v]: # extend v -> u
ndp[u] = (ndp[u] + dp[v]) % MOD
dp = ndp
return sum(dp) % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each of the n - 1 steps relaxes at most 20 edges.
💾 Space Complexity
O(1): two arrays of ten counters.
⚠️ Interview Pitfalls & Follow-ups
- Walking a full
3 x 4grid: the keypad has only ten digits, and the bottom row contains a single cell, so a naive grid traversal steps onto non-existent keys. - Allowing a knight to stay put: every transition must be a real knight move, which is why digit
5has no outgoing edges. - Deferring the modulo: the counts grow exponentially, so reduce modulo
10^9 + 7inside the loop. - Starting with a single digit: a length-1 number may end on any of the ten digits, so all start at 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.