A ideia da programação dinâmica: de baixo para cima

Inverter a viagem

A memoização parte do problema grande e desce: para achar fib de 10, ela pede fib de 9 e fib de 8, e vai descendo até bater no caso base, guardando os resultados na volta. A programação dinâmica clássica faz o caminho contrário. Ela começa pelo que já se sabe, os casos base, e sobe: primeiro fib de 2, depois fib de 3, depois fib de 4, sempre usando os dois valores anteriores que já estão na tabela, até chegar em fib de 10. Não há recursão nenhuma; é um laço simples preenchendo uma tabela do começo ao fim. As duas técnicas resolvem o mesmo problema e cortam o mesmo desperdício; mudam só a direção da viagem.

A imagem da escada ajuda a fixar. Suponha que você pode subir um ou dois degraus por vez, e quer saber de quantos jeitos diferentes dá para chegar ao topo. Em vez de pensar no degrau mais alto primeiro, comece de baixo. Ao degrau 1 só dá para chegar de um jeito. Ao degrau 2, de dois jeitos (um mais um, ou um pulo de dois). E ao degrau 3? De onde você pode dar o último passo: do degrau 2 ou do degrau 1. Então os jeitos de chegar ao 3 são a soma dos jeitos de chegar ao 2 e ao 1. Você monta cada degrau a partir dos anteriores, subindo a tabela até o topo.

Os degraus na prática

Traduzir a escada para pseudocódigo é preencher uma tabela com um laço. Você guarda quantos jeitos há de chegar a cada degrau. Começa fixando os casos base: um jeito para o degrau 1, dois jeitos para o degrau 2. Daí em diante, um laço sobe degrau por degrau, e cada posição recebe a soma das duas anteriores. Quando o laço chega ao último degrau, a resposta está lá, pronta. Repare que é exatamente a lógica do Fibonacci, só vestida de escada, e que a construção de baixo para cima dispensa a recursão inteira. É um laço, uma tabela e uma soma, resolvendo em poucos passos o que a versão ingênua faria em milhões.

funcao jeitosDeSubir(n)
  se n <= 2 entao
    retorne n   // 1 degrau: 1 jeito; 2 degraus: 2 jeitos
  fim
  tabela <- lista de tamanho n + 1
  tabela[1] <- 1
  tabela[2] <- 2
  para i de 3 ate n faca
    tabela[i] <- tabela[i - 1] + tabela[i - 2]
  fim
  retorne tabela[n]
fim
escreva(jeitosDeSubir(4))

Um laço preenche a tabela de baixo para cima. Cada degrau é a soma dos dois anteriores; sem recursão.

funcao jeitosDeSubir(n)
  se n <= 2 entao
    retorne n
  fim
  tabela <- lista de tamanho n + 1
  tabela[1] <- 1
  tabela[2] <- 2
  para i de 3 ate n faca
    tabela[i] <- tabela[i - 1] + tabela[i - 2]
  fim
  retorne tabela[n]
fim
escreva(jeitosDeSubir(4))

A mesma ideia no problema do troco

O troco mostra que a técnica vale muito além do Fibonacci. Imagine que você quer pagar um valor usando o menor número possível de moedas, com certos valores de moeda disponíveis. De baixo para cima, você resolve o troco de todo valor menor primeiro: quantas moedas, no mínimo, para 1, para 2, para 3, e assim por diante, até o valor cheio. Para cada valor, você testa cada moeda e pergunta: se eu usar esta moeda, sobra um valor menor cujo melhor troco eu já calculei e guardei; qual escolha me dá menos moedas no total? A resposta de cada valor se apoia nas respostas dos valores menores, exatamente a subestrutura ótima da aula anterior, e a tabela guarda tudo para não recalcular.