Please enable JavaScript.
Coggle requires JavaScript to display documents.
Programação dinâmica - Coggle Diagram
Programação dinâmica
-
Receita da Memoization
1. Faça funcionar
- Visualize o problema como se fosse uma árvore.
- Implemente a árvore usando recursão.
-
2. Faça-o ser eficiente
- Adicione um objeto "memo" (chave:valor).
- Adicione um caso base que retorne o valor do memo.
- Guarde os valores do "return" no memo.
-
Tipicamente, esses subproblemas surgem de uma reincidência relatando uma solução de um dado problema para soluções dos seus subproblemas menores.
Ao invés de resolver subproblemas sobrepostos de novo e de novo, a programação dinâmica sugere resolver cada um dos menores subproblemas somente uma vez e gravar os resultados em uma mesa na qual a solução para o problema original pode então ser obtida.
Um princípio geral que sublinha aplicações da programação dinâmica que lidam com problemas de otimização é o chamado princípio da otimalidade.
Que diz que, uma solução ótima para qualquer instância de um problema de otimização é composta de soluções ótimas para suas sub-instâncias.