Digit dp — очень простая техника, которая также полезна для решения многих задач динамического программирования. Увидев название «Digit DP» несложно догадаться, что мы собираемся что-то делать с цифрами. Да, мы на самом деле собираемся играть с цифрами. Существует много типов задач, которые требуют подсчета количества целых чисел 'x' между двумя целыми числами, скажем, 'a' и 'b', такими как что x удовлетворяет определенному свойству, которое может быть связано с его цифрами. Итак, если мы говорим, что G(x) указывает количество таких целых чисел от 1 до x (включительно), то количество таких целых чисел между a и b может быть задано как G(b ) — G(a-1). Именно тогда вступает в действие цифра DP (динамическое программирование). Все такие задачи подсчета целых чисел, которые удовлетворяют вышеуказанному свойству, могут быть решены с помощью подхода цифровой DP.

Ключевая концепция

  • Пусть заданное число x состоит из n цифр. Основная идея digit DP состоит в том, чтобы сначала представить цифры как массив цифр t[]. Допустим, у нас есть tntn-1tn-2 … t2t1 в качестве десятичного представления, где ti (0 ‹ i ‹= n) обозначает i-ю цифру справа. Самая левая цифра tn является старшей цифрой.
  • Теперь, после представления заданного числа таким образом, мы генерируем числа меньше заданного числа и одновременно вычисляем с помощью DP, если число удовлетворяет заданному свойству. Мы начинаем генерировать целые числа, имеющие количество цифр = 1, а затем до тех пор, пока количество цифр = n. Целые числа, имеющие меньшее количество цифр, чем n, можно проанализировать, установив крайние левые цифры равными нулю.

Давайте объясним концепцию, используя классическую задачу.

Проблема:

Сколько чисел x находится в диапазоне от a до b, где цифра d встречается точно k раз из x? Может быть несколько решений, включая теорию чисел или комбинаторику, но давайте посмотрим, как мы можем решить эту проблему, используя цифру dp.

Решение:

Решите для диапазона (от нуля до a)

Используя цифру dp, мы всегда сосредотачиваемся на построении числа, удовлетворяющего всем условиям. Если нам, наконец, удастся построить это число, мы скажем: да, оно у нас есть ;-) Но как мы будем строить это число? Пока допустим, что a равно нулю. Итак, нам нужно найти общие числа, которые не превышают b и также удовлетворяют заданным условиям.

Построение последовательности цифр

Рассмотрим число как последовательность цифр. Назовем последовательность sq. Изначально sq пуст. Мы попробуем добавить новые цифры слева направо, чтобы построить последовательность. В каждом рекурсивном вызове мы помещаем цифру в нашу текущую позицию и будем вызывать рекурсивно, чтобы добавить цифру в следующую позицию. Но можем ли мы поместить любую из цифр от 0 до 9 в нашу текущую позицию? Конечно, нет, потому что нам нужно убедиться, что число не превышает b.

Информация, необходимая для размещения цифры в текущей позиции

Допустим, во время построения последовательности мы сейчас находимся в позиции pos. Мы уже разместили несколько цифр в позиции от 1 до pos-1. Итак, теперь мы пытаемся поместить цифру в текущую позицию pos. Если бы мы знали всю последовательность, которую мы построили до позиции pos-1, то мы могли бы легко узнать, какие цифры мы можем разместить сейчас. Но как?

Вы можете видеть, что в последовательности sq самая левая цифра на самом деле является самой старшей цифрой. И значение уменьшается слева направо. Итак, если существует какая-либо позиция t (1‹=t‹pos), где sq[t] ‹ b[t], то мы можем поместить любую цифру в нашу текущую позицию. Потому что последовательность уже стала меньше, чем b, независимо от того, какую цифру мы помещаем в более поздние позиции. Обратите внимание, что b[t] означает цифру в позиции t под номером b.

Но если не было t, удовлетворяющих этому условию, то в позиции pos мы не можем разместить ни одну цифру больше, чем b[pos]. Потому что тогда число станет больше, чем b.

Нам действительно нужна вся последовательность?

А теперь представьте, действительно ли нам нужна вся эта последовательность, чтобы определить, существует ли действительный t? Если бы мы поместили любую цифру в нашу предыдущую позицию, которая была бы меньше, чем соответствующая цифра в b, то не могли бы мы просто передать информацию каким-то образом, чтобы мы могли использовать ее позже? Да, используя дополнительный параметр f1(true/false) в нашей функции, мы можем справиться с этим. Всякий раз, когда мы помещаем цифру в позицию t, которая меньше, чем b[t], мы можем сделать f1 = 1 для следующего рекурсивного вызова. Поэтому всякий раз, когда мы оказываемся в какой-либо позиции позже, нам на самом деле не нужна вся последовательность. Используя значение f1, мы можем узнать, стала ли последовательность меньше, чем b.

Дополнительное условие

До сих пор мы сосредоточились на построении последовательности sq, но забыли, что есть дополнительное условие: цифра d должна встречаться ровно k. strong> раз подряд sq. Нам нужен еще один параметр cnt. cnt — это количество раз, которое мы поместили цифру d до сих пор в нашу последовательность sq. Всякий раз, когда мы помещаем цифру d в нашу последовательность sq, мы просто увеличиваем cnt в нашем следующем рекурсивном вызове.

В базовом случае, когда мы построили всю последовательность, нам просто нужно проверить, равно ли cnt k. Если да, то мы возвращаем 1, иначе мы возвращаем 0.

Окончательные состояния DP

Если мы до сих пор все поняли, то легко увидеть, что нам нужно всего три состояния для мемоизации DP. В какой позиции мы находимся, если число уже стало меньше, чем b и частота цифры d до сих пор.

Решите для диапазона (от a до b)

Используя описанный выше подход, мы можем найти общее количество допустимых чисел в диапазоне от 0 до b. Но в исходной задаче диапазон фактически был от a до b. Как с этим справиться? Что ж, сначала мы можем найти результат для диапазона от 0 до b, а затем просто удалить результат для диапазона от 0 до a-1. . Тогда то, что мы оставили, на самом деле является результатом от диапазона a до b.

Как найти диапазон от a до b за одну рекурсию?

В приведенном выше подходе мы использовали дополнительный параметр f1, который помог нам убедиться, что последовательность не становится больше, чем b. Нельзя ли сделать то же самое, чтобы последовательность не стала меньше a? Да, конечно. Для этого нам нужно поддерживать дополнительный параметр f2, который будет говорить, существует ли позиция t такая, что sq[t] › a[t]. В зависимости от значения f2 мы можем выбрать цифры в нашей текущей позиции так, чтобы последовательность не стала меньше, чем a. Примечание. Мы также должны поддерживать условие для f1 параллельно, чтобы последовательность оставалась действительной.