Programação dinâmica

Dynamic programming is a fancy name for [recursion] with a table. Instead of solving subproblems recursively, solve them sequentially and store their solutions in a table. The trick is to solve them in the right order so that whenever the solution to a subproblem is needed, it is already available in the table. Dynamic programming is particularly useful on problems for which divide-and-conquer appears to yield an exponential number of subproblems, but there are really only a small number of subproblems repeated exponentially often. In this case, it makes sense to compute each solution the first time and store it away in a table for later use, instead of recomputing it recursively every time it is needed.

— Ian Parberry, Problems on Algorithms

 

Muitos algoritmos eficientes seguem o paradigma da programação dinâmica.  Esse paradigma, ou estratégia de projeto de algoritmos, é uma espécie de tradução iterativa inteligente da recursão e pode ser definido, vagamente, como recursão com o apoio de uma tabela.

Como em um algoritmo recursivo, cada instância do problema é resolvida a partir da solução de instâncias menores, ou melhor, de subinstâncias da instância original.  A característica distintiva da programação dinâmica é a tabela que armazena as soluções das várias subinstâncias.  O consumo de tempo do algoritmo é, em geral, proporcional ao tamanho da tabela.

(A palavra programação na expressão programação dinâmica não tem relação direta com programação de computadores.  Ela significa planejamento e refere-se à construção da tabela que armazena as soluções das subinstâncias. A propósito, veja a resposta de Shai Simonson à pergunta What does the "Dynamic" mean in Dynamic Programming? no Quora.)

Para que o paradigma da programação dinâmica possa ser aplicado, é preciso que o problema tenha estrutura recursiva:  a solução de toda instância do problema deve conter soluções de subinstâncias da instância.  Essa estrutura recursiva pode, em geral, ser representada por uma recorrência e a recorrência pode ser traduzida em um algoritmo recursivo.  O algoritmo recursivo é tipicamente ineficiente porque refaz, muitas vezes, a solução de cada subinstância.  Uma vez escrito o algoritmo recursivo, entretanto, é fácil construir uma tabela para armazenar as solução das subinstância e assim evitar que elas sejam recalculadas.  A tabela é a base de um algoritmo de programação dinâmica.

Exemplos

Eis alguns algoritmos que usam programação dinâmica:


Valid HTML 4.01 Strict Valid CSS!