Количество N-значных чисел, у которых побитовое И смежных цифр равно 0

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

Примеры:

Input: N = 1
Output: 10
Explanation: All numbers from 0 to 9 satisfy the given condition as there is only one digit.

Input: N = 3
Output: 264

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

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

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

• Определите рекурсивную функцию, скажем, countOfNumbers(digit, prev) , выполнив следующие шаги.
  • Если значение цифры равно N + 1 , то вернуть 1 , так как формируется действительное N-значное число.
  • Если результат состояния dp[digit][prev] уже вычислен, вернуть это состояние dp[digit][prev] .
  • Если текущая цифра 1 , то можно поставить любую цифру из [1, 9] . Если N = 1 , то можно поставить и 0 .
  • В противном случае выполните итерацию по всем числам от i = 0 до i = 9 и проверьте, выполняется ли условие ((i & prev) == 0) или нет, и, соответственно, поместите удовлетворяющие значения «i» в текущую позицию.
  • После корректного размещения рекурсивно вызовите функцию countOfNumbers для индекса (цифра + 1) .
  • Верните сумму всех возможных правильных размещений цифр в качестве ответа.
• В качестве результата выведите значение, возвращаемое функцией countOfNumbers(1, 0, N) .

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

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