558. Knight Dialer
A chess knight is parked on the digit pad of an old phone:
1 2 3 4 5 6 7 8 9 * 0 #
It moves the way a knight always does — two cells in one direction, then one cell sideways — and it is only ever allowed to land on the ten digit keys, never on * or #.
Drop the knight on any digit you like, then make exactly n - 1 jumps. Reading off every key it touches (starting key included) spells an n-digit sequence.
Your function receives the integer n and returns how many distinct sequences can be dialed this way. The count explodes quickly, so return it modulo 1,000,000,007.
Example 1:
Input: n = 1
Output: 10
Explanation: No jumps happen — the knight just sits on its starting key, and any of the 10 digits works.
Example 2:
Input: n = 2
Output: 20
Explanation: Add up each digit's knight moves: 4 and 6 reach three keys each, 5 reaches none, and every other digit reaches two. 3 + 3 + 0 + 7·2 = 20.
Example 3:
Input: n = 3
Output: 46
Explanation: Each 2-digit sequence extends by every legal jump from its last key, giving 46 sequences of length 3.
Constraints:
- 1 ≤ n ≤ 5000
Hints:
The board never changes, so the set of digits reachable from each digit is a fixed table you can write down once. Note that 5 has no moves at all, while 4 and 6 have three each.
How many length-k sequences end on digit d? Only the length-(k−1) counts of d's knight-neighbors matter — that recurrence is a dynamic program with just 10 states per step.
You never need more than the previous step's 10 counts, so two size-10 arrays give O(1) space.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 1
Expected output: 10