Количество различных чисел, которые может составить шахматный конь за N ходов на мобильной клавиатуре

Даны целое число N и шахматный конь , помещенный в клавиатуру мобильного телефона. Задача состоит в том, чтобы подсчитать общее количество различных N цифр, которые может составить шахматный конь за N ходов. Поскольку ответ может быть очень большим, укажите значение ответа по модулю 10 ⁹ + 7 .

Примечание: За каждый ход шахматный конь может переместиться на 2 единицы по горизонтали и на одну единицу по вертикали или на две единицы по вертикали и на одну единицу по горизонтали.

На изображении показана демонстрационная мобильная клавиатура, где «*» и «#» не считаются частью номера.

Примеры:

Input: N = 1
Output: 10
Explanation: Placing the knight over any numeric cell of the 10 cells is sufficient.

Input: N = 2
Output: 20
Explanation: All the valid number are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

Подход: Идея состоит в том, чтобы найти возможные ячейки, которые могут быть достигнуты из данной ячейки для каждой ячейки, и сложить их все, чтобы найти ответ. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте вектор v[10, 1] и temp[10] .
• Перебрать диапазон [1, N), используя переменную i , и выполнить следующие задачи:
  • Найдите значения для всех ячеек в temp[] и затем сохраните их в векторе v[].
• Инициализируйте переменную sum как 0 , чтобы сохранить ответ.
• Переберите диапазон [0, 10), используя переменную i , и выполните следующие задачи:
  • Добавьте значение v[i] к переменной sum .
• После выполнения вышеуказанных шагов выведите значение суммы в качестве ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)