dav

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Sobre o paradigma de programação dinâmica para solução de um problema, é INCORRETO afirmar:

1. As soluções ótimas do problema incluem as soluções ótimas de seus sub-problemas 
2. A solução do problema utiliza a solução de sub-problemas, como no paradigma de divisão e conquista
3. O algoritmo de programação dinamica utiliza soluções de sub-problemas armazenadas em memória para evitar o re-cálculo de sub-problemas já resolvidos.
4. Para que o algoritmo de programação dinâmica seja eficiente o numero de sub-problemas deve ser pequeno (ex: polinomial com a entrada)
5. NDA

Ideia original de: Daniel Vidal