Programação dinâmica: memoização x tabulação

Resposta esperada

PD serve quando o problema tem subestrutura ótima (a solução do todo se compõe da solução de subproblemas) E subproblemas sobrepostos (os mesmos subproblemas reaparecem — senão é só divisão e conquista). Sinal clássico: uma recursão que recalcula os mesmos argumentos (Fibonacci ingênuo, mochila, edição de string). Top-down / memoização: escreve a recursão natural e cacheia o resultado por argumento — fácil de derivar da força bruta, calcula só os subproblemas que aparecem, mas paga overhead de chamada e risco de estouro de pilha. Bottom-up / tabulação: preenche uma tabela dos casos base pra cima, na ordem das dependências — sem recursão, geralmente mais rápido e com espaço frequentemente reduzível (guardar só a última linha/coluna), mas exige descobrir a ordem de preenchimento e calcula a tabela toda mesmo que nem toda célula seja necessária.