Please enable JavaScript.
Coggle requires JavaScript to display documents.
Programação Dinâmica - Coggle Diagram
Programação Dinâmica
DP (Dynamic Programming) não é um algoritmo em si, mas uma técnica que pode ser usada para resolver certos problemas que podem ser divididos em vários subproblemas
A DP resolve cada um dos subproblemas e deixa todos os resultados obtidos armazenados em um vetor. A partir desses resultados, é possível chegar numa resposta final
Fibonacci
Basta computar todos os valores partindo do primeiro como 0 e do segundo como 1, que é possível chegar a uma resposta para o enésimo termo
-
Coin-Row problem
Como conseguir a maior quantia me dinheiro dentro de uma série de moedas de forma que nunca vão ser escolhidas duas moedas adjacentes
-
Coin-Collecting problem
Máximo números de moedas que um robô pode coletar em um tabuleiro NxM, começando do extremo superior esquerdo e podendo se movimentar apenas para a direita ou para baixo
-
Problemas NP e NP-difíceis, mesmo que ainda não possam ser resolvidos em tempo polinomial, algumas aproximações podem ser feitas para tentar resolvê-los em tempos mais rápidos, mesmo que a solução não seja a mais ideal
Essa aproximação se baseia na heurística, ou seja, uma regra que não foi matematicamente provada, mas que foi percebida a partir de várias experiências e teste.
Alguns exemplos de problemas que são resolvidos dessa maneira são os do caixeiro viajante (traveling salesman) e da mochila (knapsack)