Problema B - Para Cima e Para Baixo

Tipo de problema: Programação Dinâmica
Autor do Problema: Pedro Ribeiro (DCC/FCUP)

Problema:
De quantas maneiras conseguimos construir o número pedido?

Restrições:
1 <= D <= 1 000.
1 <= M <= 2 000 000 000.

Solução base:
Se soubermos quantos '?' são, podemos fazer esse número de ciclos de 0 até 9 e validar o número.
Gerar os números recursivamente e validar daria aproximadamente 30 pontos.

Gerar só os números válidos:
Conhecendo a solução recursiva anterior, parece evidente que podemos gerar somente os números válidos.
Esta solução daria aproximadamente 50 pontos.

Agrupar '?'s:
Podemos reaproveitar muita coisa!

Imaginem o número 183???583???5.

Conseguem ver onde reaproveitar os cálculos? Só precisamos de calcular o número de possibilidades nos pontos de interrogação uma única vez e multiplicar!

Esta solução daria aproximadamente 70 pontos.

Programação dinâmica:
Na solução anterior já conseguimos perceber que certos cálculos podem ser reaproveitados.

Na realidade, a única coisa que precisamos de saber é:

Pode-se construir esta matriz usando os valores anteriores, e a resposta está indicada no último valor!

Ligações interessantes: