Neste tutorial, você aprenderá o que é programação dinâmica. Além disso, você encontrará a comparação entre programação dinâmica e algoritmos gananciosos para resolver problemas.
A Programação Dinâmica é uma técnica de programação de computador que ajuda a resolver com eficiência uma classe de problemas que têm subproblemas sobrepostos e propriedade de subestrutura ótima.
Esses problemas envolvem o cálculo repetido do valor dos mesmos subproblemas para encontrar a solução ideal.
Exemplo de programação dinâmica
Considere o caso da geração da sequência de fibonacci.
Se a sequência for F (1) F (2) F (3)… F (50), segue a regra F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46) …
Observe como há subproblemas sobrepostos, precisamos calcular F (48) para calcular F (50) e F (49). Este é exatamente o tipo de algoritmo em que a Programação Dinâmica se destaca.
Como funciona a programação dinâmica
A programação dinâmica funciona armazenando o resultado dos subproblemas para que, quando suas soluções forem necessárias, eles estejam disponíveis e não seja necessário recalculá-los.
Essa técnica de armazenar o valor dos subproblemas é chamada de memoização. Ao salvar os valores no array, economizamos tempo para cálculos de subproblemas que já encontramos.
var m = map (0 → 0, 1 → 1) função fib (n) se a chave n não estiver no mapa mm (n) = fib (n - 1) + fib (n - 2) return m (n)
A programação dinâmica por memoização é uma abordagem de cima para baixo para a programação dinâmica. Ao inverter a direção em que o algoritmo funciona, ou seja, começando do caso base e trabalhando em direção à solução, também podemos implementar a programação dinâmica de baixo para cima.
função fib (n) se n = 0 retornar 0 else var prevFib = 0, currFib = 1 repetir n - 1 vezes var newFib = prevFib + currFib prevFib = currFib currFib = newFib retornar atualFib
Recursão vs programação dinâmica
A programação dinâmica é principalmente aplicada a algoritmos recursivos. Isso não é uma coincidência, a maioria dos problemas de otimização requer recursão e programação dinâmica é usada para otimização.
Mas nem todos os problemas que usam recursão podem usar a Programação Dinâmica. A menos que haja a presença de subproblemas sobrepostos, como no problema da sequência de fibonacci, uma recursão só pode chegar à solução usando uma abordagem de dividir para conquistar.
Essa é a razão pela qual um algoritmo recursivo como Merge Sort não pode usar a Programação Dinâmica, porque os subproblemas não se sobrepõem de forma alguma.
Algoritmos Greedy vs Programação Dinâmica
Os Algoritmos Greedy são semelhantes à programação dinâmica no sentido de que ambos são ferramentas de otimização.
No entanto, algoritmos gananciosos procuram soluções localmente ótimas ou, em outras palavras, uma escolha gananciosa, na esperança de encontrar um ótimo global. Conseqüentemente, algoritmos gananciosos podem fazer uma suposição que pareça ótima no momento, mas se torna cara no futuro e não garante um ótimo global.
A programação dinâmica, por outro lado, encontra a solução ótima para os subproblemas e, em seguida, faz uma escolha informada para combinar os resultados desses subproblemas para encontrar a solução mais ótima.
