mediumDynamic Programming 1DPure DSA~30 min
Count Knight-Jump Phone Numbers
A chess knight hops across a phone keypad, dialing a digit at each landing. Count how many distinct n-digit numbers it can dial.
Problem
A knight on a standard phone keypad (digits 0-9 in the usual 3x4 layout with * and # corners unusable) starts on any numeric cell and makes n-1 valid knight moves, dialing the digit it lands on each time. Return the number of distinct n-digit sequences modulo 1e9+7.
Input
An integer n (the number of digits dialed).
Output
An integer: the count of distinct dialable numbers modulo 1e9+7.
Constraints
- 1 <= n <= 5000
- Answer is taken modulo 1_000_000_007.
Examples
Example 1
Input
n = 1
Output
10
Any of the ten digits is a valid 1-digit number.
Example 2
Input
n = 2
Output
20
Twenty valid two-digit sequences via single knight moves.