Programação dinâmica: como resolver problemas complexos com memoização

Programação dinâmica (DP — Dynamic Programming) é uma técnica para otimizar algoritmos que resolvem problemas com subestrutura ótima e subproblemas sobrepostos. Em termos simples: quando um problema pode ser dividido em subproblemas menores, e esses subproblemas se repetem, programação dinâmica resolve cada subproblema apenas uma vez e armazena o resultado para reutilização — eliminando cálculos redundantes que tornariam soluções ingênuas exponencialmente lentas. DP aparece em praticamente todas as entrevistas técnicas de nível sênior das grandes empresas e é um tema central em competições de programação.

O padrão: identificar subproblemas sobrepostos

Um problema tem subproblemas sobrepostos quando a solução recursiva ingênua recalcula os mesmos valores múltiplas vezes. Fibonacci é o exemplo mais claro: fib(5) chama fib(3) duas vezes e fib(2) três vezes. Com DP, cada valor é calculado uma única vez.

Abordagem top-down: memoização

def coin_change(moedas, alvo, memo={}):
    """
    Problema clássico de DP: menor número de moedas para atingir o valor alvo.
    Exemplo: moedas=[1, 5, 10], alvo=27 → 4 moedas: 10+10+5+2(1+1)
    """
    if alvo == 0:
        return 0
    if alvo < 0:
        return float('inf')
    if alvo in memo:
        return memo[alvo]

    minimo = float('inf')
    for moeda in moedas:
        resultado = coin_change(moedas, alvo - moeda, memo)
        minimo = min(minimo, resultado + 1)

    memo[alvo] = minimo
    return minimo

print(coin_change([1, 5, 10], 27))  # 4
print(coin_change([1, 5, 10], 11))  # 2 (10 + 1)

Abordagem bottom-up: tabulação

A abordagem bottom-up constrói a solução de baixo para cima, preenchendo uma tabela iterativamente — sem recursão, sem risco de stack overflow:

def coin_change_dp(moedas, alvo):
    """
    Bottom-up DP: tabela dp[i] = menor número de moedas para valor i.
    """
    dp = [float('inf')] * (alvo + 1)
    dp[0] = 0  # Base: 0 moedas para valor 0

    for valor in range(1, alvo + 1):
        for moeda in moedas:
            if moeda <= valor:
                dp[valor] = min(dp[valor], dp[valor - moeda] + 1)

    return dp[alvo] if dp[alvo] != float('inf') else -1

print(coin_change_dp([1, 5, 10], 27))  # 4

Problema da mochila (Knapsack) — DP clássica

def knapsack(capacidade, pesos, valores, n):
    """
    Problema da mochila 0/1: itens com peso e valor — maximizar valor dentro da capacidade.
    dp[i][w] = valor máximo usando os primeiros i itens com capacidade w.
    """
    dp = [[0] * (capacidade + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacidade + 1):
            # Opção 1: não pegar o item i
            dp[i][w] = dp[i-1][w]
            # Opção 2: pegar o item i (se couber)
            if pesos[i-1] <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w - pesos[i-1]] + valores[i-1])

    return dp[n][capacidade]

pesos  = [2, 3, 4, 5]
valores = [3, 4, 5, 6]
capacidade = 8
print(knapsack(capacidade, pesos, valores, len(pesos)))  # 10

Como reconhecer se um problema é de DP

Sinais de que um problema pode ser resolvido com DP: o problema pede um máximo, mínimo ou contagem de algo, pode ser dividido em subproblemas que se sobrepõem, e tem subestrutura ótima (a solução ótima do todo depende das soluções ótimas das partes). O processo para resolver: 1. Defina o estado — o que dp[i] ou dp[i][j] representa. 2. Defina a relação de recorrência — como um estado depende dos anteriores. 3. Defina o caso base. 4. Implemente bottom-up. Problemas clássicos para praticar: Longest Common Subsequence (LCS), Longest Increasing Subsequence (LIS), Edit Distance, Coin Change, Knapsack.