Em computação a programação dinâmica é um método utilizado para a construção de algoritmos capazes de resolver problemas computacionais. Este método é aplicável aos problemas cuja solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada.
A solução anterior é memorizada para evitar recálculo.
Desta forma a programação dinâmica ou DP (Dynamic Programming) resolve um problema a partir de subproblemas que sobrepostos compõem o problema original.
Um problema computacional pode ser resolvido por DP se possuir duas características denominadas (1) subestrutura ótima e (2) superposição de subproblemas. Um problema apresenta uma subestrutura ótima quando uma solução para o problema contém em seu interior soluções para subproblemas - isto é temos a mesma fórmula de recorrência. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes - é aí que entra a memorização.
A DP não é uma forma intuitiva de pensar, portanto temos que ver diversos exemplos para conseguir compreender e assimilar como ela trabalha. Vou criar a partir de agora um conjunto de posts que mostram como solucionar alguns problemas usado DP. Estes posts virão com uma implementação completa em Java para o problema. O primeiro da série busca descobrir de quantas maneiras é possível dar um troco (N) utilizando um determinado conjunto de moedas.
Nenhum comentário:
Postar um comentário