# Contar sem enumerar

> Quantos números entre A e B têm alguma propriedade nos dígitos? A DP de dígitos responde sem olhar um por um.

- Autor: Marcello Oliveira (https://mrcll.me/about/)
- Publicado: 31 de out. de 2026
- Temas: ICPC, Fundamentos
- URL: https://mrcll.me/pt/stories/digit-dp/

Quantos números até 1.000 não têm o dígito 4 e nunca contêm “13”? Dá para conferir os mil. A resposta é 712, e você chega nela visitando 9 estados.

Primeiro, um intervalo são dois prefixos: a contagem de [A, B] é a de [0, B] menos a de [0, A−1]. Então você só precisa contar de zero até algum N.

Dentro de [0, N], monte o número a partir do dígito mais significativo e carregue uma flag, tight, que diz se você ainda está colado no limite. Se N é 723 e você coloca 7 primeiro, o próximo dígito só vai até 2. Coloque 6 primeiro e você está livre: daí em diante vale qualquer coisa de 0 a 9.

> Figura interativa (DigitDP): use a versão web em https://mrcll.me/pt/stories/digit-dp/

Por que a memorização compensa? Pense num número de 18 dígitos que termina em 0123456789. Todo prefixo possível na frente desse final leva à mesma pergunta sobre os mesmos dígitos restantes, 10⁸ cálculos idênticos se você refizer toda vez. Guarde uma vez e consulte.

O estado continua pequeno: a posição, o que a pergunta precisa lembrar (aqui, se o último dígito foi 1) e o tight. A quantidade de estados depende de quantos dígitos N tem, não do tamanho de N. Antes de enumerar qualquer coisa, pergunte qual é o menor estado que resume tudo o que veio antes.