Questão da prova oral 081 - semana 6 - Programação Dinâmica

Enunciado:
Sobre o tempo de execução de um algoritmo de Programação Dinâmica, é INCORRETO afirmar que:

A) A versão recursiva do algoritmo, geralmente, repete a resolução de diversos subproblemas para a escolha da solução ótima, realizando chamadas recursivas para a resoulção de seus subproblemas de uma forma botton-up. Esta peculiaridade, entre outras, leva seu tempo de execução á ordem de crescimento exponencial.
B) Depende, diretamente, do número de chamadas recursivas que seu algoritmo, na versão recursiva, executa.
C) Depende de dois fatores: o número de subproblemas globais e quantas escolhas são necessárias para resolução de cada subproblema.
D) Sua versão não-recursiva sempre terá melhor desempenho que sua versão recursiva, pois na primeira, é possível "otimizar" a resolução de cada subproblema pois, como eles são superpostos, utilizam da resolução já calculada de subproblemas "anteriores"
E) NDA.

Autor: Ivan Brunetto