Numero:
Sobre a técnica de programação dinâmica e os problemas os quais ela se aplica, podemos dizer que:
a. Dizemos que um problema possui subestrutura ótima quando podemos dividi-lo em problemas menores cujas soluções são superpostas
b. Alguns dos problemas onde é possível utilizar a técnica de divide-and-conquer são bons candidatos para o uso da programação dinâmica caso seja garantido a independência dos subproblemas.
c. Dada a matriz A(i,p) de (sub)soluções ótimas, usada por um algoritmo que emprega a programação dinâmica, o custo deste algoritmo sempre é dominado assintoticamente por O(i*p).
d. Se a solução de um problema pode ser obtida através das escolhas das melhores soluções dos subproblemas, podemos aplicar a programação dinâmica apenas se aquela escolha foi feita com uma abordagem top-down .
e. N.D.A
Ideia original de: Otávio Augusto Araújo Silva
Nenhum comentário:
Postar um comentário