Please enable JavaScript.
Coggle requires JavaScript to display documents.
Programação Dinâmica - Coggle Diagram
Programação Dinâmica
-
Exemplo básico:
Fibonacci
-
Diferente do algoritmo para resolução de Fibonacci normal, utilizando da programação dinâmica, é utilizada uma tabela f[0...n] para armazenar os números de Fibonacci à medida que os mesmos são calculados. Sem que haja a necessidade desse retrabalho no calculo, melhorando assim o desempenho do algoritmo.
O que é?
A programação dinâmica é uma técnica para resolver problemas com subproblemas sobrepostos. Normalmente, esses subproblemas surgem de uma recorrência relacionando a solução de um determinado problema às soluções de seus subproblemas menores.
Como funciona?
Em vez de resolver subproblemas sobrepostos repetidamente, a programação dinâmica sugere resolver cada um dos subproblemas menores apenas uma vez e registrar os resultados em uma tabela a partir da qual uma solução para o problema original pode então ser obtida.
Faz uso de uma espécie de tradução iterativa inteligente da recursão, e pode ser visto como o uso de recursão com apoio de uma tabela.
Mas, o problema é um problema de programação dinâmica?
É necessário abordar duas características, são elas:
-
-
