Подсчитайте N-значные числа, содержащие все возможные цифры хотя бы один раз

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

Примеры :

Input: N = 10
Output : 3265920

Input: N = 5
Output: 0
Explanation: Since the number of digits is less than the minimum number of digits required [0-9], the answer is 0.

Наивный подход: самый простой подход к решению задачи — сгенерировать все возможные N -значные числа и для каждого такого числа проверить, удовлетворяют ли все его цифры требуемому условию или нет.
Временная сложность: O(10 ^N *N)
Вспомогательное пространство: O(1)

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

Выполните следующие шаги, чтобы решить эту проблему:

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

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

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