Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCM 2018

Programação Dinâmica: Memoização na abordagem Top-Down

Gabarito: letra A. A memoização na estratégia Top-Down (recursiva) de programação dinâmica armazena resultados de subproblemas já resolvidos, evitando recomputações e reduzindo a complexidade de tempo exponencial para polinomial, desde que haja subproblemas sobrepostos. Essa é a definição clássica.

A questão testa o entendimento da combinação entre recursão, eficiência polinomial e sobreposição de subproblemas — tripé da programação dinâmica top-down.

Análise das alternativas

Alternativa A — ✅ Correta ⟵ GABARITO

A frase "recursivo, em tempo polinomial, para resolver subproblemas sobrepostos" descreve exatamente o papel da memoização: transformar uma recursão exponencial (que recalcula os mesmos subproblemas várias vezes) em um algoritmo polinomial, ao guardar os resultados numa tabela (memo) e consultá-los quando o mesmo subproblema reaparecer. É a essência da programação dinâmica top-down.

Alternativa B — ❌ Incorreta

Afirma que a memoização implementa um algoritmo recursivo em tempo exponencial para subproblemas não sobrepostos. Dois erros: (1) se os subproblemas não são sobrepostos, a memoização não traz ganho — cada subproblema é único e seria resolvido uma única vez mesmo na recursão ingênua, mantendo a complexidade original; (2) mesmo em subproblemas sobrepostos, se a memoização é aplicada corretamente, o tempo deixa de ser exponencial (torna-se polinomial). A alternativa mistura os conceitos de forma incorreta.

Alternativa C — ❌ Incorreta

Apresenta a memoização como um algoritmo iterativo em tempo exponencial para subproblemas sobrepostos. A abordagem iterativa (bottom-up) é outra forma de implementar programação dinâmica, sem uso de memoização (usa-se um vetor/tabela preenchida de baixo para cima). Além disso, se houver sobreposição, a abordagem iterativa também é polinomial. O termo "exponencial" contradiz o propósito da programação dinâmica.

Alternativa D — ❌ Incorreta

Diz que a memoização implementa um algoritmo iterativo em tempo polinomial a partir de uma implementação recursiva exponencial. A transformação de recursivo para iterativo (como eliminar recursão usando pilha explícita) não é função da memoização. A memoização mantém a estrutura recursiva (top-down), apenas adiciona caching. A descrição se aproxima mais de uma "iteratização" do que de memoização, que é o que a banca está cobrando.

Alternativa E — ❌ Incorreta

Afirma que a memoização gera um algoritmo iterativo polinomial a partir de um recursivo já polinomial. Se a recursão já é polinomial, não há necessidade de memoização para melhorar a complexidade – ela pode ser usada para evitar overhead de recálculo, mas não muda a ordem de grandeza. Além disso, a saída é descrita como iterativa, enquanto a memoização é tipicamente usada na versão recursiva. A alternativa confunde o propósito.

Gabarito: letra A.