Programação dinâmica (DP) resolve problemas com subproblemas sobrepostos e subestrutura ótima computando cada subproblema uma vez e reutilizando o resultado. Os dois estilos são memoização (top-down) e tabulação (bottom-up).
Recursão ingênua recomputa os mesmos subproblemas exponencialmente. DP os coloca em cache, transformando trabalho exponencial em polinomial.
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| Memoização | Tabulação | |
|---|---|---|
| Direção | recursão top-down | iteração bottom-up |
| Computa | apenas estados necessários | todos os estados |
| Risco | estouro de pilha | nenhum |
| Espaço | pode ser reduzido | frequentemente reduzível a O(1) linhas |
Fibonacci: de O(2ⁿ) ingênuo para O(n) tempo, O(n) (ou O(1)) espaço.
Use DP quando subproblemas se sobrepõem. Defina o estado e a recorrência cuidadosamente — essa é a parte difícil. Se subproblemas não se sobrepõem, divisão e conquista simples é suficiente.
DP converte problemas exponenciais intratáveis — caminhos mais curtos, distância de edição, knapsack — em eficientes.
A habilidade de identificar estado e recorrência está entre as mais valorizadas em entrevistas de algoritmos.
Ela está presente em sistemas reais desde ferramentas de diff até alinhamento de sequências em bioinformática.