Questão 66533

Uma professora de Algoritmos e Estruturas de Dados, em um curso de graduação, está ensinando sobre a técnica de programação dinâmica. Ela nota que os alunos, mesmo após entenderem a solução recursiva para problemas como o de Fibonacci, têm dificuldade em compreender a necessidade e o funcionamento da memoização (ou do método tabular). Para eles, a otimização parece uma complicação desnecessária. Para ilustrar o ganho de performance de forma dramática, ela planeja uma aula prática. Primeiro, ela apresenta um trecho de um livro sobre algoritmos: "A programação dinâmica é tipicamente aplicada a problemas de otimização que podem ser divididos em subproblemas sobrepostos. Uma abordagem recursiva ingênua resolve o mesmo subproblema várias vezes, levando a uma complexidade exponencial. A memoização, uma técnica 'top-down', armazena o resultado de cada subproblema em um cache (como um dicionário ou array) na primeira vez que é resolvido. As chamadas subsequentes para o mesmo subproblema simplesmente retornam o valor do cache em tempo constante. Isso reduz a complexidade de tempo de forma drástica, geralmente para polinomial, ao custo de um aumento no uso de espaço." A atividade consiste em os alunos implementarem duas versões de uma função para calcular o n-ésimo número de Fibonacci: uma recursiva ingênua e outra recursiva com memoização. Em seguida, eles devem medir o tempo de execução de ambas para calcular `fib(40)`.

Qual é o resultado esperado do experimento e a principal lição sobre programação dinâmica que ele ensina?