The "Knight Dialer" problem is based on a numeric keypad arranged as follows:
1 2 3
4 5 6
7 8 9
0
A chess knight starts on any digit and makes n-1 moves. In each move, it hops to another digit using the standard chess knight's "L" move (two steps in one direction and one in a perpendicular direction). The knight cannot move off the keypad.
The task is: Given an integer n, return the total number of distinct phone numbers of length n that can be dialed by the knight, modulo 10^9 + 7. Each phone number is a sequence of digits, where each digit is determined by the knight's position after each move. The knight can start on any digit.
Constraints:
1 ≤ n ≤ 5000
At first glance, a brute-force approach might seem feasible: simulate every possible sequence of knight moves for n steps, starting from every digit. However, since the number of possible sequences grows exponentially with n, this quickly becomes impractical for larger values of n.
To optimize, we should notice that the knight's position after each move depends only on its previous position and the number of moves remaining. This is a classic setup for dynamic programming (DP), where we can cache and reuse results for overlapping subproblems. The key insight is to compute, for each digit and each step, the number of ways the knight can reach that digit in that many steps.
Instead of recalculating the same subproblems repeatedly (as in recursion), we can build up the solution iteratively using a table, where each entry represents the number of ways to reach a digit after a certain number of moves.
We use dynamic programming to solve the problem efficiently. Here’s how:
dp[step][digit] represent the number of distinct sequences of length step+1 ending at digit.prev and curr.step = 0 (the first digit), there's one way to be at each digit: prev[d] = 1 for all d.n-1, for each digit, sum the ways to reach it from all previous positions it can be reached from (using the knight's move list).curr for the current step, then swap prev and curr for the next iteration.prev[d] for all digits d to get the total number of sequences of length n.10^9 + 7.This approach leverages the overlapping subproblems and optimal substructure properties of the problem, making it both time and space efficient.
Let's walk through the case where n = 2:
prev[d] = 1 for all digits d (the knight can start on any digit).curr[0] = prev[4] + prev[6] = 1 + 1 = 2.curr[0] + curr[1] + ... + curr[9] to get the answer.n = 2, the answer is 20.
This process scales efficiently for larger n due to the DP table.
Brute-force approach:
O(8^n), since the knight can make up to 8 moves from each digit at each step.n.O(n * 10), since we process 10 digits for each of n steps.O(10) (or O(2*10)), since we only need to keep the current and previous states for all digits.n up to 5000.
The Knight Dialer problem is a classic example of using dynamic programming to efficiently solve a problem with overlapping subproblems and optimal substructure. By modeling the keypad as a graph and tracking the knight's possible moves with a DP table, we avoid exponential blowup and can compute the number of valid sequences for large n. The solution is elegant, efficient, and highlights the power of DP in combinatorial counting problems.
class Solution:
def knightDialer(self, n: int) -> int:
MOD = 10**9 + 7
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]
}
prev = [1] * 10
for _ in range(n - 1):
curr = [0] * 10
for digit in range(10):
for nei in moves[digit]:
curr[digit] = (curr[digit] + prev[nei]) % MOD
prev = curr
return sum(prev) % MOD
class Solution {
public:
int knightDialer(int n) {
const int MOD = 1e9 + 7;
vector<vector<int>> moves = {
{4,6}, // 0
{6,8}, // 1
{7,9}, // 2
{4,8}, // 3
{0,3,9}, // 4
{}, // 5
{0,1,7}, // 6
{2,6}, // 7
{1,3}, // 8
{2,4} // 9
};
vector<long long> prev(10, 1), curr(10, 0);
for (int step = 1; step < n; ++step) {
fill(curr.begin(), curr.end(), 0);
for (int digit = 0; digit < 10; ++digit) {
for (int nei : moves[digit]) {
curr[digit] = (curr[digit] + prev[nei]) % MOD;
}
}
prev.swap(curr);
}
long long res = 0;
for (int count : prev) res = (res + count) % MOD;
return (int)res;
}
};
class Solution {
public int knightDialer(int n) {
int MOD = 1000000007;
int[][] moves = {
{4,6}, // 0
{6,8}, // 1
{7,9}, // 2
{4,8}, // 3
{0,3,9}, // 4
{}, // 5
{0,1,7}, // 6
{2,6}, // 7
{1,3}, // 8
{2,4} // 9
};
long[] prev = new long[10];
Arrays.fill(prev, 1);
long[] curr = new long[10];
for (int step = 1; step < n; ++step) {
Arrays.fill(curr, 0);
for (int digit = 0; digit < 10; ++digit) {
for (int nei : moves[digit]) {
curr[digit] = (curr[digit] + prev[nei]) % MOD;
}
}
long[] temp = prev;
prev = curr;
curr = temp;
}
long res = 0;
for (long count : prev) res = (res + count) % MOD;
return (int)res;
}
}
var knightDialer = function(n) {
const MOD = 1e9 + 7;
const moves = [
[4,6], // 0
[6,8], // 1
[7,9], // 2
[4,8], // 3
[0,3,9], // 4
[], // 5
[0,1,7], // 6
[2,6], // 7
[1,3], // 8
[2,4] // 9
];
let prev = new Array(10).fill(1);
let curr = new Array(10).fill(0);
for (let step = 1; step < n; ++step) {
curr.fill(0);
for (let digit = 0; digit < 10; ++digit) {
for (let nei of moves[digit]) {
curr[digit] = (curr[digit] + prev[nei]) % MOD;
}
}
[prev, curr] = [curr, prev];
}
return prev.reduce((a, b) => (a + b) % MOD, 0);
};