Knight Dialer

medium dp

Problem

A chess knight moves on a phone keypad (digits 0–9). Starting anywhere, count length-n dial sequences mod 10⁹ + 7.

Inputn = 2

Output20

Define adjacency from the keypad geometry. dp[step][key] = sum of dp[step-1][neighbours of key].

def knightDialer(n):
    MOD = 10**9 + 7
    moves = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]]
    dp = [1] * 10
    for _ in range(n - 1):
        nxt = [0] * 10
        for d in range(10):
            for m in moves[d]:
                nxt[m] = (nxt[m] + dp[d]) % MOD
        dp = nxt
    return sum(dp) % MOD

function knightDialer(n) {
  const MOD = 1_000_000_007n;
  const moves = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]];
  let dp = new Array(10).fill(1n);
  for (let s = 1; s < n; s++) {
    const nxt = new Array(10).fill(0n);
    for (let d = 0; d < 10; d++) for (const m of moves[d]) nxt[m] = (nxt[m] + dp[d]) % MOD;
    dp = nxt;
  }
  return Number(dp.reduce((a, b) => (a + b) % MOD, 0n));
}

class Solution {
    public int knightDialer(int n) {
        final long MOD = 1_000_000_007L;
        int[][] moves = { {4,6},{6,8},{7,9},{4,8},{3,9,0},{},{1,7,0},{2,6},{1,3},{2,4} };
        long[] dp = new long[10];
        Arrays.fill(dp, 1);
        for (int s = 1; s < n; s++) {
            long[] nxt = new long[10];
            for (int d = 0; d < 10; d++) for (int m : moves[d]) nxt[m] = (nxt[m] + dp[d]) % MOD;
            dp = nxt;
        }
        long total = 0;
        for (long v : dp) total = (total + v) % MOD;
        return (int)total;
    }
}

int knightDialer(int n) {
    const long long MOD = 1000000007LL;
    vector<vector<int>> moves = { {4,6},{6,8},{7,9},{4,8},{3,9,0},{},{1,7,0},{2,6},{1,3},{2,4} };
    vector<long long> dp(10, 1);
    for (int s = 1; s < n; s++) {
        vector<long long> nxt(10, 0);
        for (int d = 0; d < 10; d++) for (int m : moves[d]) nxt[m] = (nxt[m] + dp[d]) % MOD;
        dp = nxt;
    }
    long long total = 0;
    for (auto v : dp) total = (total + v) % MOD;
    return (int)total;
}

Explanation

Imagine a chess knight hopping around a phone keypad. We want to count how many different n-digit numbers it can dial, where each step is a legal knight move. Trying every sequence would explode, so we count smartly with dynamic programming.

The trick is that the answer only depends on which key you are currently on, not the path you took to get there. So dp[d] holds the number of valid sequences of the current length that end on digit d.

We start with dp = [1]*10 because a length-1 dial can begin on any of the ten keys. Then we repeat n-1 times: for each digit d we push its count into every neighbor reachable by a knight move, using the precomputed moves adjacency list. All sums are taken modulo 10^9 + 7.

Example: for n = 2, every key contributes its single sequence to its neighbors, and summing the final dp gives 20 two-digit dials.

Each round just folds in one knight move across the fixed keypad, so the work is O(n) with only a tiny fixed array of size 10.

Time: O(n) Space: O(1)