Programação Dinâmica (Dynamic Programming)

Definição

Programação Dinâmica (Dynamic Programming) é uma técnica de otimização usada para resolver problemas complexos ao quebrá-los em subproblemas menores, resolvê-los uma única vez e armazenar os resultados para evitar recomputações.

É ideal quando o problema possui:

O mesmo subproblema aparece várias vezes (subproblemas sobrepostos);
A melhor solução do todo depende das melhores soluções das partes (subestrutura ótima).

Por que usar

Evita cálculos repetidos e melhora a performance;
Aumenta muito a eficiência de soluções recursivas;
Pode transformar algoritmos muito lentos (exponenciais) em soluções bem mais rápidas (polinomiais).

Exemplos clássicos

Sequência de Fibonacci;
Problema da mochila 0/1;
Subsequência comum máxima (LCS);
Cadeia de multiplicação de matrizes.

Abordagens

Top-down (com Memoization): usa recursão com cache para armazenar resultados já calculados;
Bottom-up (tabulação): preenche uma tabela de forma iterativa, de baixo para cima.

Exemplo prático (Python) — Fibonacci com programação dinâmica

def fibonacci_dp(n):
    if n <= 1:
        return n

    fib = [0] * (n + 1)
    fib[1] = 1

    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]

    return fib[n]

print(fibonacci_dp(8))  # Saída: 21

Visualização (Bottom-Up)

Para n = 5:

fib[0] = 0
fib[1] = 1
fib[2] = 1
fib[3] = 2
fib[4] = 3
fib[5] = 5
fib[6] = 8
fib[7] = 13
fib[8] = 21