Questão de Algoritmos e Estrutura de Dados

Sempre que um algoritmo recursivo apresenta subproblemas sobrepostos, a estratégia adequada é divisão e conquista, pois a independência entre subproblemas evita recomputações.

A memoização é uma abordagem iterativa de baixo para cima: percorre todos os subproblemas em ordem crescente de tamanho, armazenando cada resultado sequencialmente em tabela antes de resolver qualquer subproblema de tamanho maior.

A tabulação resolve, de forma iterativa, apenas os subproblemas que seriam efetivamente alcançados pela versão recursiva do mesmo algoritmo, evitando computações desnecessárias com estados inatingíveis

Divisão e conquista e programação dinâmica são estratégias equivalentes: ambas subdividem o problema em partes menores, resolvem cada parte e combinam os resultados — a diferença é apenas notacional, não algorítmica.

A memoização é uma estratégia top-down: aplicada a algoritmos recursivos, armazena o resultado de cada subproblema na primeira vez que é calculado, reutilizando-o em chamadas subsequentes; a tabulação é bottom-up e preenche a tabela iterativamente em ordem crescente de tamanho de subproblema.