Подсчитайте N-значные числа, у которых соседние цифры имеют равный НОД

Для данного положительного целого числа N задача состоит в том, чтобы найти количество всех N -значных чисел, соседние цифры которых имеют одинаковый наибольший общий делитель (НОД).

Примеры:

Input: N = 2
Output: 90
Explanation:
All 2-digit numbers satisfy the condition as there is only one pair of digits and there are 90 2-digit numbers.

Input: N = 3
Output: 457

Наивный подход: Самый простой подход к решению данной задачи состоит в том, чтобы сгенерировать все возможные N-значные числа и подсчитать те числа, соседние цифры которых имеют одинаковый НОД. После проверки всех чисел выведите значение count как результирующее общее количество чисел.

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

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью динамического программирования, поскольку в приведенной выше задаче есть перекрывающиеся подзадачи и оптимальная подструктура. Подзадачи могут быть сохранены в мемоизации таблицы dp[][][], где dp[index][prev][gcd] хранит ответ с позиции index ^th до конца, где prev используется для хранения предыдущей цифры числа gcd — это НОД между существующими соседними цифрами в номере. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте глобальный многомерный массив dp[100][10][10] со всеми значениями как -1 , в котором хранится результат каждого рекурсивного вызова.
• Определите рекурсивную функцию, скажем, countOfNumbers(index, prev, gcd, N) и выполните следующие шаги:
  • Если значение индекса равно (N + 1) , то вернуть 1 , так как сформировано действительное N -значное число.
  • Если результат состояния dp[index][prev][gcd] уже вычислен, верните это значение dp[index][prev][gcd] .
  • Если текущий индекс равен 1 , то можно поставить любую цифру из [1-9] .
  • Если текущий индекс больше 1 , можно поместить любую цифру от [0-9] .
  • Если индекс больше 2 , можно поставить цифру, если НОД текущей цифры и предыдущей цифры равен НОД уже существующих соседних цифр.
  • После правильного размещения цифр рекурсивно вызовите функцию countOfNumbers для (index + 1) .
  • Верните сумму всех возможных правильных размещений цифр в качестве ответа.
• В качестве результата выведите значение, возвращаемое функцией countOfNumbers(1, 0, 0, N) .

Ниже приведена реализация вышеуказанного подхода:

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