⚡Flashcard Drill➔
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

  1. Model the keypad as a graph: each digit is a node and a knight move is an edge.
  2. Let dp[v] be the number of distinct length-i numbers ending on digit v; then dp_next[u] = sum(dp[v]) over every v that can jump to u.
  3. The move graph is fixed, so each step costs a constant amount of work across the ten digits.
  4. A length-1 number can end on any digit, so every dp[v] starts at 1; the answer is sum(dp) after n steps.

💻 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 4 grid: 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 5 has no outgoing edges.
  • Deferring the modulo: the counts grow exponentially, so reduce modulo 10^9 + 7 inside 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems