Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória. 1 Ela é aplicável a problemas nos quais a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada - de forma a evitar recálculo - de outros subproblemas que, sobrepostos, compõem o problema original.
O que um problema de otimização deve ter para que a programação dinâmica seja aplicável são duas principais características: subestrutura ótima e superposição de subproblemas. Um problema apresenta uma subestrutura ótima quando uma solução ótima para o problema contém em seu interior soluções ótimas para subproblemas. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes.
Uma das estratégias de resolução algoritmica de problemas mais difíceis de ser aplicada, na minha opinião, é a programação dinâmica. Mas existem alguns truques que facilitam o desenvolvimento de algoritmos baseados nessa idéia.
A maior dificuldade de se usar este método é encontrar a poderosíssima fórmula de recorrência. Uma vez encontrada, o algoritmo está quase pronto. O problema é que, para encontrar a fórmula de recorrência, é preciso pensar recursivamente, afinal programação dinâmica é praticamente uma recursão memorizada.
Programadores muitas das vezes dão de cara com alguns problemas que devem ser resolvidos com uma solução melhor. A solução de um problema já pode até existir mas pode não ser a melhor ou a mais rápida solução possível, várias companhias estão interessadas em pessoas que conseguem desenvolver algoritmos que aumente a velocidade de execução dos programas. Se uma companhia qualquer tiver um programa de grande importância que é usado diariamente por vários de seus clientes e o algoritmos que está por trás executa em tempo exponencial, essa companhia com certeza pagará bem por um algoritmo que execute em tempo polinômial. Então procure aprender Programação Dinâmica pra não passar fome! (nem tanto neh…)
Programação Dinâmica muita das vezes é mal interpretado por muitas pessoas pensando que é o nome de um algoritmo, mas na realidade é o nome de uma técnica de programação avançada que você pode usar para escrever um bom algoritmo. Programação dinâmica no começo parece mágica pois conseguimos ver o que está acontecendo mas não sabemos como fazer até aplicarmos a técnica em alguns exemplos. Existem dois tipos de programação dinâmica: (bottom-up) resolve os problemas de pequena dimensão e guarda as soluções; solução de um problema é obtida combinando as de problemas de menor dimensão ou (top-down/divisão e conquista) o problema é partido em subproblemas que se resolvem separadamente; solução obtida por combinação das soluções.
Exemplo: Abaixo está um figura de como seria calcular o n-ésimo numero fibonacci sem a técnica de programação dinâmica, nessa figura seria o n seria 6.
Note que exite grupos de problemas que já foram resolvidos mas que seram calculados novamente. O sub-problema F4 esta sendo calculado do lado esquerdo e direito da árvore. O F3, F2 e F1 também estão sendo recalculados, isto é traduzido para perca de tempo.
Algoritmo usando programação dinâmica (botton-up):
BONS ESTUDOS!!
Fonte: (Wikipedia e blog leonardonunes)
