Sobre programação dinâmica, assinale a alternativa CORRETA:

A) A programação dinâmica e o método de dividir e conquistar são muito semelhantes: ambos particionam o problema em subproblemas independentes.

B) Informalmente, o tempo de execução de um algoritmo de programação dinâmica depende do número de subproblemas globais, já que o número de escolhas observadas para cada subproblema é o mesmo para todos os algoritmos.

C) Por meio da programação dinâmica, problemas que, quando resolvidos recursivamente, possuíam tempo exponencial podem ter esse tempo reduzidos a grandezas polinomiais.

D) A programação dinâmica, assim como o método de dividir e conquistar, são abordagens top-down (de cima para baixo).

E) N.D.A.

Autor: Camila Ribeiro Rocha
RA: 022247