Mas o que car@%!0$ é Programação Dinâmica?

Vamos entender mais sobre esse tipo de algoritmo e quando ele pode ser útil!

Resumindo, programação dinâmica é um tipo de algoritmo que utiliza de memorização para evitar calcular a mesma coisa duas vezes. Para fazer isso, basta que você use uma estrutura de dados auxiliar, como um array ou uma matriz para armazenar respostas já computadas de subproblemas que compõem o problema principal.

Esse tipo de algoritmo pode ser aplicado em problemas definidos por subproplemas menores, como sequências recursivas, tal qual a de Fibonacci, que usaremos como exemplo aqui.

Na sequência de Fibonacci (aqui representada pela função fib(n) e começando a contar os termos a partir de 0), temos 2 termos predefinidos: fib(0)=0 e fib(1)=1. Para n>1, temos fib(n)=fib(n-1)+fib(n-2). Podemos fazer uma implementação recursiva relativamente simples da sequência, como podemos ver no código abaixo:

Código em C representando uma implementação recursiva, sem fazer uso de programação dinâmica, da sequência de Fibonacci.

Mas qual o problema dessa implementação?

Sim, ela funciona, mas gera uma árvore de recursão muito grande, tornando o cálculo de um termo muito demorado para um n grande o suficiente devido a múltiplos cálculos do mesmo número de Fibonacci. Para calcular fib(5), por exemplo, temos a seguinte árvore de recursão:

Árvore de recursão mostrando as chamadas recursivas da função fib(n) necessárias para calcular fib(5)

Note que fib(5) e fib(4) são calculados apenas uma vez. Até aí tudo bem. Mas, fib(3) é cálculado 2 vezes, fib(2) 3 vezes, fib(1) 4 vezes e fib(0) 3 vezes.

“Recalcular” fib(0) e fib(1) não é um problema, pois já temos esses valores como padrão, não precisamos realizar de fato algum cálculo. Mas, conforme n cresce, tendemos a ter que recalcular valores cada vez mais vezes. Tente calcular fib(45) utilizando esse programa, por exemplo. Aposto que seu computador, independente do quão bom seja, vai levar um tempo bem acima do normal esperado para fazer isso.

Certo. Entendemos que estamos recalculando muitas vezes o mesmo valor e que isso é ruim. Mas, e agora? Como podemos evitar múltiplos cálculos do mesmo valor?

É aí que entra a programação dinâmica.

Se armazenarmos todos os valores calculados num vetor de memorização, podemos apenas extrair os resultados armazenados nesse vetor ao invés de termos de os recalcular. Observe o código abaixo, que segue esse princípio:

Funções utilizando programação dinâmica para calcular valores da sequência de Fibonacci. Devido a limitações de nossos computadores, só podemos calcular valores até fib(46), dado que fib(47) em diante excedem o máximo valor de inteiro.

A criação desse código é menos intuitiva e mais complexa do que a do primeiro. Mas, elimina a necessidade de calcular duas vezes o mesmo valor, tornando nossa implementação significativamente mais rápida.

Um detalhe interessante sobre a programação dinâmica é que ela possibilita duas aproximações distintas para os problemas: top-down, que consiste em resolver o problema “de cima para baixo”, recursivamente, como é mostrado no exemplo acima e também a aproximação bottom-up (de baixo para cima), que é iterativa, como podemos ver no exemplo abaixo:

Função em C utilizando programação dinâmica para calcular um número de Fibonacci utilizando-se da aproximação bottom-up.

Ainda poderíamos fazer diversas modificações. Na aproximação bottom-up, poderíamos, por exemplo, utilizar o array auxiliar apenas para os 2 valores anteriores ao da atual iteração no loop for, diminuindo a complexidade de espaço, e ainda poderíamos considerar o algoritmo como programação dinâmica, visto que ele não repete cálculos por meio do uso de estratégias de PD.

Há muita teoria envolvida em programação dinâmica na qual não entrei nesse artigo. Porém, quando eu tive de estudar o assunto, o exemplo da sequência de Fibonacci foi como finalmente comecei a entender. É recomendado que você aplique a programação dinâmica em problemas com subestrutura ótima, ou seja, cuja solução ótima para o problema é obtida combinando as soluções ótimas de subproblemas, para que possa evitar cálculos repetidos da mesma resposta do mesmo subproblema.

O melhor jeito de entender PD de verdade é a exercitando em diversos problemas. Como casos de estudo, recomendo:

• O Problema da Multiplicação de Cadeia de Matrizes,
• O Problema da Mochila
• O Problema do Troco

Os códigos dos exemplos, bem como seus executáveis já compilados, estão disponíveis em meu Github.

Espero que esse breve texto sirva de ponto de partida para você que tem interesse em estudar programação dinâmica ou que possa esclarecer as suas dúvidas se você já começou. Esse é um tópico muito comum na programação competitiva e mesmo em entrevistas de emprego, então, seu estudo sem dúvida alguma é importante. Que tal começar agora mesmo?