Динамика по цифрам (digit DP): флаг tight и подсчёт чисел в диапазоне

Digit DP простыми словами: как посчитать числа из [L, R] с условием на цифры при R до 10¹⁸, зачем нужен флаг tight, как убрать ведущие нули и что мемоизировать. Код на Python.

12 мин чтенияалгоритмы · динамическое программирование · python

Коротко

ПараметрЗначение
Когда применять«Сколько чисел в [L,R][L, R] обладают свойством X», а RR до 101810^{18} и больше
Главный приёмОтвет =f(R)−f(L−1)= f(R) - f(L-1), где f(N)f(N) — сколько подходящих чисел в [0,N][0, N]
СостояниеПозиция цифры, флаг tight, «память» о префиксе (сумма, маска, остаток…)
СложностьO(длина⋅состояния⋅10)O(\text{длина} \cdot \text{состояния} \cdot 10) — обычно десятки тысяч операций
  • Число строится цифра за цифрой слева направо, а не перебирается целиком.
  • Флаг tight говорит, совпадает ли уже построенный префикс с префиксом NN. Пока совпадает, следующая цифра ограничена цифрой NN, после первого отклонения ограничений нет.
  • Всё, что условие требует помнить о префиксе, становится частью состояния. Мемоизация склеивает одинаковые состояния, и вместо 101810^{18} чисел остаются сотни или тысячи вариантов.

Как узнать задачу

Формулировки похожи друг на друга:

  • сколько чисел от 1 до NN не содержат цифру 4;
  • сколько чисел в [L,R][L, R] имеют сумму цифр, кратную kk;
  • сколько раз цифра 1 встречается во всех числах от 0 до NN;
  • сколько чисел до NN состоят из попарно различных цифр;
  • сколько чисел до NN не имеют двух единиц подряд в двоичной записи.

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

Если хотя бы одного из трёх нет, скорее всего это не digit DP. Например, «сколько простых в [1,1012][1, 10^{12}]» — условие на величину, его по цифрам не проверить.

Шаг 1: от диапазона к префиксу

Считать сразу на [L,R][L, R] неудобно: тогда нужно следить за двумя границами одновременно. Стандартный трюк тот же, что в префиксных суммах:

count(L,R)=f(R)−f(L−1),\text{count}(L, R) = f(R) - f(L - 1),

где f(N)f(N) — количество подходящих чисел в [0,N][0, N]. Дальше задача — посчитать f(N)f(N) для одного числа.

Наивно это цикл:

def f_naive(n: int) -> int: return sum('4' not in str(x) for x in range(n + 1))

При N=106N = 10^6 это работает, при N=1018N = 10^{18} — нет. Зато наивное решение пригодится позже как эталон для проверки.

Шаг 2: интуиция флага tight

Возьмём N=235N = 235 и посчитаем числа от 0 до 235 без цифры 4. Будем считать каждое число трёхзначным с ведущими нулями: 7 — это 007. Для условия «нет цифры 4» нули ничего не портят.

Выбираем первую цифру:

  • 0 или 1. Число уже точно меньше 235, на остальные позиции можно ставить что угодно, кроме 4: по 9 вариантов. Итого 2⋅9⋅9=1622 \cdot 9 \cdot 9 = 162.
  • 2. Совпали с первой цифрой NN. Мы всё ещё «прижаты» к границе, следующая цифра не может быть больше 3.
    • Вторая цифра 0, 1 или 2: отклонились вниз, третья свободна, 3⋅9=273 \cdot 9 = 27.
    • Вторая цифра 3: снова прижаты, третья от 0 до 5, кроме 4, — это 5 вариантов.
  • 3–9 нельзя: число станет больше 235.

Итого 162+27+5=194162 + 27 + 5 = 194.

Состояние «прижаты к границе» и есть tight. Правило перехода одно:

новый tight = старый tight И (выбранная цифра == цифре N на этой позиции)

Как только tight стал False, обратно он не вернётся: если префикс уже меньше, число меньше, что бы мы ни дописали. Поэтому tight = True в каждой позиции бывает ровно на одном пути — на том, который повторяет NN цифра в цифру. Почти вся работа приходится на «свободные» состояния, и именно их выгодно кешировать.

Шаг 3: шаблон

Перебор из примера превращается в рекурсию с мемоизацией:

from functools import lru_cache def count_no_four(n: int) -> int: digits = list(map(int, str(n))) @lru_cache(maxsize=None) def dfs(pos: int, tight: bool) -> int: if pos == len(digits): return 1 # дописали число до конца — оно подходит limit = digits[pos] if tight else 9 total = 0 for d in range(limit + 1): if d == 4: continue total += dfs(pos + 1, tight and d == limit) return total return dfs(0, True) print(count_no_four(235)) # 194

Каждая задача на digit DP — этот же каркас с тремя местами для правки:

  1. Что добавить в состояние. Здесь ничего, кроме pos и tight: условие «нет четвёрки» проверяется на каждой цифре и памяти о префиксе не требует.
  2. Какие цифры запрещены и как меняется состояние при выборе цифры d.
  3. Что вернуть в конце, когда pos == len(digits): 1 или 0 в зависимости от накопленного состояния.

Функция dfs(pos, tight, ...) отвечает на вопрос: «сколькими способами можно дописать цифры с позиции pos до конца, если префикс уже вот такой». Это обычная динамика: состояние, переходы, база.

Ответ включает 0. Если по условию числа начинаются с 1, вычтите единицу или учтите это в базе, см. раздел про ведущие нули.

Пример: сумма цифр кратна k

Теперь условие зависит от всего префикса. Хранить саму сумму можно, но достаточно остатка по модулю kk: дальше важен только он.

from functools import lru_cache def count_sum_div(n: int, k: int) -> int: digits = list(map(int, str(n))) @lru_cache(maxsize=None) def dfs(pos: int, rem: int, tight: bool) -> int: if pos == len(digits): return 1 if rem == 0 else 0 limit = digits[pos] if tight else 9 total = 0 for d in range(limit + 1): total += dfs(pos + 1, (rem + d) % k, tight and d == limit) return total return dfs(0, 0, True) def count_in_range(left: int, right: int, k: int) -> int: below = count_sum_div(left - 1, k) if left > 0 else 0 return count_sum_div(right, k) - below print(count_in_range(1, 100, 10)) # 9: 19, 28, 37, 46, 55, 64, 73, 82, 91 print(count_sum_div(10**18, 7)) # 142857142856594042

При N=1018N = 10^{18} и k=7k = 7 состояний 19⋅7⋅2=26619 \cdot 7 \cdot 2 = 266, у каждого до 10 переходов. Две с половиной тысячи операций вместо 101810^{18}.

Обратите внимание на left > 0: при left = 0 вызов count_sum_div(-1, k) сломается на str(-1), потому что первым «символом» окажется минус.

Ведущие нули: флаг started

В задаче про сумму цифр ведущие нули безвредны: 007 и 7 дают одну и ту же сумму. Но так бывает не всегда. Возьмём числа с попарно различными цифрами (LeetCode 2376, Count Special Integers). Число 7, записанное как 007, содержит два нуля, и без особой обработки мы его потеряем.

Решение — ещё один флаг started: началось ли число, была ли уже ненулевая цифра. Пока started = False, ноль означает «цифры здесь нет», и в маску он не попадает.

from functools import lru_cache def count_special(n: int) -> int: """Числа от 1 до n с попарно различными цифрами.""" digits = list(map(int, str(n))) @lru_cache(maxsize=None) def dfs(pos: int, mask: int, tight: bool, started: bool) -> int: if pos == len(digits): return 1 if started else 0 # «пустое» число 0 не считаем limit = digits[pos] if tight else 9 total = 0 for d in range(limit + 1): if not started and d == 0: # ведущий ноль: число ещё не началось, маску не трогаем total += dfs(pos + 1, mask, tight and d == limit, False) elif not mask >> d & 1: total += dfs(pos + 1, mask | 1 << d, tight and d == limit, True) return total return dfs(0, 0, True, False) print(count_special(20)) # 19: все от 1 до 20, кроме 11 print(count_special(135)) # 110

Маска из 10 бит хранит, какие цифры уже были, — та же идея, что в ДП по подмножествам, а операции с ней разобраны в статье про битовые манипуляции. Состояний не больше 10⋅210⋅2⋅2≈4110 \cdot 2^{10} \cdot 2 \cdot 2 \approx 41 тысячи, реально достижимых намного меньше.

Флаг started нужен, когда условие смотрит на сами цифры или их соседство: различные цифры, «нет двух одинаковых подряд», «цифры не убывают», чётность длины. Для сумм, остатков и запрета ненулевой цифры можно обойтись без него.

Пример: считаем не числа, а цифры

LeetCode 233 (Number of Digit One) спрашивает, сколько раз цифра 1 встречается во всех числах от 0 до NN. Отвечать нужно не количеством чисел, а суммой по ним. Каркас тот же, меняется база: в конце возвращаем не 1, а количество единиц, накопленное на пути.

from functools import lru_cache def count_digit_one(n: int) -> int: digits = list(map(int, str(n))) @lru_cache(maxsize=None) def dfs(pos: int, ones: int, tight: bool) -> int: if pos == len(digits): return ones limit = digits[pos] if tight else 9 total = 0 for d in range(limit + 1): total += dfs(pos + 1, ones + (d == 1), tight and d == limit) return total return dfs(0, 0, True) print(count_digit_one(13)) # 6: 1, 10, 11 (две), 12, 13

Счётчик ones не больше длины числа, поэтому состояний по-прежнему мало. Есть и вариант без счётчика: dfs возвращает пару «сколько чисел, сколько единиц в них», и при выборе d = 1 к сумме добавляется количество чисел-продолжений. Он экономнее по состояниям, но писать его на собеседовании дольше, а ошибиться проще.

Пример: другая система счисления

Digit DP не привязан к десятичной записи. LeetCode 600 (Non-negative Integers without Consecutive Ones): сколько чисел от 0 до NN не содержат в двоичной записи двух единиц подряд. Берём биты вместо цифр, верхняя граница свободной цифры — 1, в состояние добавляем предыдущий бит.

from functools import lru_cache def find_integers(n: int) -> int: bits = list(map(int, bin(n)[2:])) @lru_cache(maxsize=None) def dfs(pos: int, prev: int, tight: bool) -> int: if pos == len(bits): return 1 limit = bits[pos] if tight else 1 total = 0 for b in range(limit + 1): if prev == 1 and b == 1: continue total += dfs(pos + 1, b, tight and b == limit) return total return dfs(0, 0, True) print(find_integers(5)) # 5: 0, 1, 10, 100, 101

Ведущие нули здесь снова безвредны: ноль никогда не создаёт пару «11». Кстати, свободная часть этой задачи — числа Фибоначчи: строк длины mm без двух единиц подряд ровно Fm+2F_{m+2}. Это та же рекуррента, что в задаче о ступеньках, только digit DP выводит её за вас.

Две границы сразу и большие числа в строках

Иногда LL и RR даны строками длиной до 22 знаков, а ответ нужно взять по модулю 109+710^9 + 7, как в LeetCode 2719 (Count of Integers: сумма цифр от min_sum до max_sum). Вычитать единицу из строки неудобно, и есть два пути.

Путь 1. Считать f(R)−f(L)+[L подходит]f(R) - f(L) + [L \text{ подходит}]: проверить само LL проще, чем вычесть из него единицу. При работе по модулю разность может уйти в минус, поэтому в конце берите (a - b) % MOD: в Python результат будет неотрицательным, в C++ и Java нужно добавить MOD перед взятием остатка (подробнее — в статье про модульную арифметику).

Путь 2. Вести два флага: tight_hi прижимает сверху к RR, tight_lo снизу к LL, а LL дополняется ведущими нулями до длины RR.

from functools import lru_cache MOD = 10**9 + 7 def count_between(num1: str, num2: str, min_sum: int, max_sum: int) -> int: n = len(num2) low = list(map(int, num1.zfill(n))) # выравниваем нижнюю границу нулями high = list(map(int, num2)) @lru_cache(maxsize=None) def dfs(pos: int, s: int, tight_lo: bool, tight_hi: bool) -> int: if s > max_sum: return 0 # отсечение: сумма уже не уменьшится if pos == n: return 1 if s >= min_sum else 0 lo = low[pos] if tight_lo else 0 hi = high[pos] if tight_hi else 9 total = 0 for d in range(lo, hi + 1): total += dfs(pos + 1, s + d, tight_lo and d == lo, tight_hi and d == hi) return total % MOD return dfs(0, 0, True, True) print(count_between('1', '12', 1, 8)) # 11: все от 1 до 12, кроме 9

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

Итеративная версия

Рекурсия с lru_cache читается легко, но в языках без удобной мемоизации или при жёстком лимите времени пишут таблицу. Идея прямая: идём по цифрам слева направо и храним cnt[r] — сколько свободных префиксов (уже строго меньше префикса NN) имеют остаток r. Путь tight единственный, поэтому для него хватает одной переменной.

def count_sum_div_table(n: int, k: int) -> int: digits = list(map(int, str(n))) cnt = [0] * k # свободные префиксы по остаткам суммы tight_rem = 0 # остаток префикса, совпадающего с N for limit in digits: new = [0] * k for r in range(k): if cnt[r]: for d in range(10): new[(r + d) % k] += cnt[r] for d in range(limit): # отклоняемся от N вниз — префикс становится свободным new[(tight_rem + d) % k] += 1 cnt = new tight_rem = (tight_rem + limit) % k return cnt[0] + (1 if tight_rem == 0 else 0) # плюс само число N print(count_sum_div_table(10**18, 7)) # 142857142856594042 — как у рекурсии

Здесь хорошо видно, что tight — это не «ещё одно измерение таблицы», а один-единственный путь, от которого на каждой позиции отходят ветки в свободную часть.

Что именно мемоизировать

В шаблонах выше tight входит в ключ кеша, и это корректно. В решениях на C++ часто встречается другой вариант: кешируют только состояния с tight = False, а прижатые вычисляют каждый раз заново.

if (!tight && memo[pos][rem] != -1) return memo[pos][rem]; // ... перебор цифр ... if (!tight) memo[pos][rem] = total;

Так делают по двум причинам:

  • прижатых состояний всего длина\text{длина} штук, кешировать их бессмысленно;
  • свободные состояния не зависят от NN: «сколькими способами дописать 5 любых цифр, чтобы остаток стал 0» — одно и то же для любой границы. Поэтому таблицу memo можно не очищать между вызовами f(R)f(R) и f(L−1)f(L-1) и даже между тестами, если длина числа выравнивается до максимальной.

Это верно, только пока pos отсчитывается так, что одинаковым значениям соответствует одинаковое число оставшихся цифр. Если RR и L−1L-1 разной длины, pos = 2 значит у них разное. Надёжный приём — индексировать по количеству оставшихся цифр: rem_len = len(digits) - pos.

В Python с lru_cache проще: функция dfs создаётся заново внутри каждого вызова f(n), и кеш живёт ровно один вызов.

Сложность

O(D⋅S⋅B),O(D \cdot S \cdot B),

где DD — число цифр (≤19\le 19 для int64, log⁡BN\log_B N в общем случае), SS — количество значений «памяти о префиксе» вместе с флагами, BB — основание системы, то есть переходов на шаг.

ЗадачаСостояниеПорядок числа операций при N=1018N = 10^{18}
Нет цифры 4pos, tight19⋅2⋅1019 \cdot 2 \cdot 10
Сумма кратна kkpos, rem, tight19⋅k⋅2⋅1019 \cdot k \cdot 2 \cdot 10
Различные цифрыpos, mask, tight, startedдо 19⋅1024⋅4⋅1019 \cdot 1024 \cdot 4 \cdot 10
Количество единицpos, ones, tight19⋅19⋅2⋅1019 \cdot 19 \cdot 2 \cdot 10

Память — число состояний. Глубина рекурсии равна количеству цифр, так что sys.setrecursionlimit не нужен.

Типичные ошибки

Забыли обновить tight. Пишут dfs(pos + 1, ..., d == limit) вместо tight and d == limit. Тогда после отклонения от NN флаг может «включиться» обратно, и часть чисел потеряется.

f(L - 1) при L = 0. Отрицательное число в str() даёт минус в списке цифр. Обрабатывайте этот случай отдельно: f(−1)=0f(-1) = 0.

Ведущие нули там, где они важны. Различные цифры, «нет одинаковых соседей», «цифры строго возрастают» — без started число 7 превращается в 007 и проваливает проверку.

Ноль в ответе. Шаблон честно считает число 0 (путь «все нули»). Если по условию диапазон от 1, его нужно вычесть или не засчитывать в базе при started = False.

Кеш, общий для разных NN. Если @lru_cache висит на функции верхнего уровня, которая читает глобальный digits, второй вызов вернёт ответы от первого числа. Объявляйте dfs внутри или передавайте границу явно.

Хранят лишнее. Сумма цифр вместо остатка, полное число вместо остатка по модулю — состояний становится в десятки раз больше. Спросите себя: что из префикса на самом деле влияет на ответ?

Где встречается

Digit DP редко дают на скрининге, но он регулярно появляется в разделе Hard на LeetCode и в контестах. Всё решается одним шаблоном:

ЗадачаЧто в состоянии
233. Number of Digit Oneсчётчик единиц
357. Count Numbers with Unique Digitsмаска цифр, started (решается и формулой)
600. Non-negative Integers without Consecutive Onesпредыдущий бит, основание 2
902. Numbers At Most N Given Digit Setstarted, цифры из заданного набора
1012. Numbers With Repeated Digitsдополнение к задаче о различных цифрах
2376. Count Special Integersмаска цифр, started
2719. Count of Integersсумма цифр, две границы, модуль
2827. Number of Beautiful Integers in the Rangeразность чётных и нечётных, остаток, started

Если на интервью попалась такая задача, проговорите план вслух: «свожу к f(R)−f(L−1)f(R) - f(L-1), иду по цифрам слева направо с флагом tight, в состоянии держу X, потому что условие зависит от X». Это сразу показывает, что вы знаете технику, и интервьюер обычно соглашается до того, как вы напишете первую строку.

Последний совет — проверка. Наивный sum(... for x in range(n + 1)) пишется за минуту. Прогоните оба решения на случайных NN до нескольких тысяч: ошибки с tight, нулями и границами всплывают сразу. Подход «сначала перебор, потом оптимизация» подробнее разобран в статье «Как решать незнакомую задачу», а близкие комбинаторные трюки — в комбинаторике для программистов.

Потренироваться в спокойной обстановке

Все задачи