Programação dinâmica

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. 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.

Exemplos

Como exemplo simples de programação dinâmica, com alguma frequência, alguns textos, utilizam a determinação da
Sequência de Fibonacci, quando implementada de forma recursiva. Isso porque quando a forma recursiva é implementada
sem maiores cuidados, sem memorização, o seu cálculo de tempo cresce exponencialmente. Observe que a rigor esse caso não é um problema de programação dinâmica, visto que o cálculo do n-ésimo número
de Fibonacci cresce linearmente, e não exponencialmente. Porém este exemplo ainda assim é utilizado, pois a
simplicidade é grande.

    Se  n <= 1  então           F(n) :=   1
                caso contrário  F(n) := F(n-1) + F(n-2)

Quando implementada de forma recursiva "ingênua" (naive), sem memorização, a dupla chamada à F na segunda linha,
causa a necessidade da repetição de cálculos, que cresce exponencialmente.