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

Дана натуральное число N , задача состоит в том, чтобы подсчитать количество N -значных чисел, сумма цифр которых является простым числом.

Примеры:

Input: N = 1
Output: 4
Explanation: [2, 3, 5, 7] are single digit numbers whose sum of digits is equal to a prime number.

Input : N = 2
Output : 33

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

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

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

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

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

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