Программа курса:
Задача 9: Шахматный конь
Напишите определение функции knightDialer(n: int) -> int, которая принимает целое число n — длину номера телефона, и возвращает количество различных номеров телефона длины n, которые можно набрать с помощью шахматного коня, начиная с любого числа на телефонной клавиатуре.
Шахматный конь может перемещаться по телефону в соответствии с его уникальным движением, которое описано следующим образом: он может перемещаться на два квадрата по вертикали и один по горизонтали, или на два квадрата по горизонтали и один по вертикали, образуя букву "L". Конь может только находиться на числовых ячейках (то есть на синих ячейках, представленных на телефоне).
Возвращаемое значение должно быть остатком от деления на 10^9 + 7, так как ответ может быть очень большим.
Пример 1:
Входные данные:
n = 1
Выходные данные:
10
Пояснение: Мы должны набрать номер длины 1, поэтому размещение коня на любой из 10 ячеек достаточно.
Пример 2:
Входные данные:
n = 2
Выходные данные:
20
Пояснение: Все возможные действительные номера, которые мы можем набрать, включают: [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94].
Пример 3:
Входные данные:
n = 3131
Выходные данные:
136006598
Пояснение: Обратите внимание на модуль.