Knight on a Phone Keypad

Medium

A phone keypad is laid out like this:

A chess knight is placed on one of the keys. It moves in an L shape: two cells vertically and one horizontally, or two horizontally and one vertically. It may only land on digit keys; the blank spots to the left and right of 0 are off limits. The starting key is the first digit of the number, and every key the knight jumps to appends one more digit. How many distinct numbers of length length can be dialed this way (exactly length - 1 moves, starting from any key)? The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

length=1 → 10

A one-digit number is just the key the knight starts on: 10 options.

Example 2

length=2 → 20

The moves are 0→4, 0→6, 1→6, 1→8, 2→7, 2→9, 3→4, 3→8, 4→0, 4→3, 4→9, 6→0, 6→1, 6→7, 7→2, 7→6, 8→1, 8→3, 9→2, 9→4, 20 in total. From key 5 the knight cannot jump anywhere.

Example 3

length=4 → 104

Constraints

1 ≤ length ≤ 5000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Dynamic Programming

Similar problems

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium

Input

length=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 45 tests on the server, hidden ones included.