Gabarito A
Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória. Ela é aplicável a problemas nos quais a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada - de forma a evitar recálculo - de outros subproblemas que, sobrepostos, compõem o problema original.
O que um problema de otimização deve ter para que a programação dinâmica seja aplicável são duas principais características: subestrutura ótima e superposição de subproblemas. Um problema apresenta uma subestrutura ótima quando uma solução ótima para o problema contém em seu interior soluções ótimas para subproblemas. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes.
Problemas de programação dinâmica podem ser abordados de forma top-down ou bottom-up.
Top Down
Como os próprios nomes sugerem, a abordagem top-down aborda o problema de forma recursiva comum, ou seja, no exemplo do algoritmo de Fibonacci (mais abaixo), começamos pelo n-ésimo número e em, recursivamente, ir calculando os valores de F[ n-1 ], F[ n-2 ], F[ n-3 ],..., F[ 2 ], F[ 1 ]. Nesta abordagem, os valores são armazenados em uma tabela e, para a i-ésima iteração, verifica-se se F[ i ] já foi calculado.
Bottom Up
Na abordagem bottom-up, vamos calculando os subproblemas menores e aumentando a complexidade com o passar do tempo, ou seja, para o exemplo de Fibonacci, começaríamos calculando F[ 1 ], depois F[ 2 ], F[ 3 ], e assim por diante até F[ n ]. Observe que, nesta abordagem, na nós sabemos que, na i-ésima iteração, F[ i-1 ] já foi resolvido, logo não precisamos verificar toda vez como na top-down. Ao consultar o exemplo 1, do Algortimo de Fibonacci, isso deve ficar mais claro.
Em geral, ambas as abordagens tem o mesmo tempo assintótico de execução.
"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !