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

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

Примеры:

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: 495

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

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

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

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

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

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