Em Produção · ICPC · Fundamentos
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.
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.
Carregando a figura interativa…
Versão estática: até 1.000 existem 712 números sem o dígito 4 e sem “13”, calculados com 9 estados de 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.