A respeito da Programação Dinâmica, analise as afirmativas a seguir. I. A solução ótima do problema provém das soluções de subproblemas dependentes. II. Na abordagem bottom-up, a solução parte da solução geral ótima. III. A solução ótima passa pela resolução de subproblemas que aparecem uma única vez. Está correto o que se afirma em
- A)I, apenas.
Correta, porque na programação dinâmica a solução ótima é construída a partir das soluções de subproblemas dependentes, combinando resultados parciais.
- B)II, apenas.
Errada, porque a abordagem bottom-up parte dos casos menores para chegar à solução final, e não da solução geral ótima.
- C)III, apenas.
Errada, porque a técnica se beneficia justamente de subproblemas que se repetem, e não de problemas que aparecem uma única vez.
- D)I e II, apenas.
- E)II e III, apenas.
Gabarito: A
Programação dinâmica é uma técnica de resolução de problemas em que você quebra um problema grande em subproblemas menores, mas com uma condição importantíssima: esses subproblemas precisam se repetir e a solução do todo depende das soluções parciais. A ideia é guardar resultados para não refazer conta, como quem anota a resposta no caderno para não recalcular a mesma coisa toda hora. Em geral, isso aparece em problemas com subestrutura ótima e subproblemas sobrepostos, muito comuns em algoritmos, otimização e pesquisa operacional.