#935

Knight Dialer

specialist · 695 · lc medium +30 · verified · 61.8% accepted · 3,199 likes · top 62%

Description

A chess knight sits on a phone dialpad with keys 0–9 and moves according to standard knight-jump rules. Starting on any digit, count the total number of distinct n-digit phone numbers that can be dialed with exactly n - 1 knight jumps. Return the result modulo 10⁹ + 7.

Example 1:

Input: n = 1

Output: 10

Explanation: We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.

Example 2:

Input: n = 2

Output: 20

Explanation: All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

Example 3:

Input: n = 3131

Output: 136006598

Explanation: Please take care of the mod.

Code

1

2

3

class Solution:
    def knightDialer(self, n: int) -> int:

class Solution:
    def knightDialer(self, n: int) -> int: