DAA - Programação Dinâmica

A Programação Dinâmica também é usada em problemas de otimização. Como o método dividir e conquistar, a Programação Dinâmica resolve problemas combinando as soluções de subproblemas. Além disso, o algoritmo de Programação Dinâmica resolve cada subproblema apenas uma vez e salva sua resposta em uma tabela, evitando assim o trabalho de recalcular a resposta todas as vezes.

Duas propriedades principais de um problema sugerem que o problema determinado pode ser resolvido usando a Programação Dinâmica. Essas propriedades sãooverlapping sub-problems and optimal substructure.

Subproblemas sobrepostos

Semelhante à abordagem Dividir e Conquistar, a Programação Dinâmica também combina soluções para subproblemas. É usado principalmente onde a solução de um subproblema é necessária repetidamente. As soluções calculadas são armazenadas em uma tabela, para que não tenham que ser recalculadas. Conseqüentemente, essa técnica é necessária quando existe subproblema sobreposto.

Por exemplo, a pesquisa binária não tem subproblemas de sobreposição. Considerando que o programa recursivo de números de Fibonacci tem muitos subproblemas sobrepostos.

Subestrutura Ótima

Um dado problema possui uma Propriedade de Subestrutura Ótima, se a solução ótima do problema dado pode ser obtida usando soluções ótimas de seus subproblemas.

Por exemplo, o problema do caminho mais curto tem a seguinte propriedade de subestrutura ideal -

Se um nó x encontra-se no caminho mais curto de um nó de origem u para o nó de destino v, então o caminho mais curto de u para v é a combinação do caminho mais curto de u para x, e o caminho mais curto de x para v.

Os algoritmos padrão de caminho mais curto de todos os pares, como Floyd-Warshall e Bellman-Ford, são exemplos típicos de programação dinâmica.