Programação Dinâmica com dígitos [Pt 3]: Editorial

Vamos aqui abordar dois problemas que são bons exemplos de PD com dígitos e não são fáceis:

Spoj NUMTSN: 369 Numbers (link para o problema)
Codeforces 2015-2016 Petrozavodsk Winter Training Camp: Maximum Product (link para o problema)

Programação Dinâmica com dígitos [Pt 2]

Na parte 1, vimos como resolver o problema de quantos números existem entre 0 e B com uma propriedade, e dissemos que para computar de A a B basta fazer de 0 a B menos de 0 a A-1. O problema é que nem sempre dá certo. Por exemplo, se quisessemos o número entre A e B com maior soma de dígitos, essa estratégia não funcionaria!

Vamos agora ver como resolver de outra forma então, mais genérica, mas que pode ser mais lenta.

Como exemplo, vamos usar o problema: quantos números menores que X e maiores que Y existem tal que a soma dos dígitos é exatamente 20.

Programação Dinâmica com dígitos [Pt 1]

Programação dinâmica (PD) em dígitos é uma subclasse dos problemas de PD. Existem muitas variações, nessa parte falamos da forma: Dado um intervalo A e B, quantos números x, A <= x <= B, tem uma propriedade específica.

No nosso caso, vamos usar o problema: quantos números menores que X existem tal que a soma dos dígitos é exatamente 20. Existem várias formas de resolver, e irei mostrar uma.