Programação Dinâmica

Programação dinâmica (dynamic programming, DP) é uma técnica de projeto de algoritmos para resolver problemas de otimização e contagem ao dividi-los em subproblemas, resolver cada subproblema uma única vez e reutilizar esses resultados. A DP é especialmente valiosa na inteligência artificial (artificial intelligence, AI) porque muitos problemas de busca, planejamento e inferência probabilística (probabilistic inference) podem ser expressos como “melhor forma de chegar a um estado (state)” ou “melhor explicação de uma sequência”, o que naturalmente leva a subcálculos reutilizáveis.

O que é Programação Dinâmica (e o que não é)

Em alto nível, a DP se aplica quando:

  • O problema tem subestrutura ótima (optimal substructure): uma solução ótima pode ser composta a partir de soluções ótimas de subproblemas.
  • O problema tem subproblemas sobrepostos (overlapping subproblems): os mesmos subproblemas surgem repetidamente ao longo da árvore de recursão/busca.

A DP costuma ser contrastada com:

  • Dividir e conquistar (divide and conquer): os subproblemas são, em geral, independentes (por exemplo, mergesort). Na DP, os subproblemas se sobrepõem fortemente.
  • Busca em grafos (graph search): explora um espaço de estados; a DP tipicamente explora uma estrutura (muitas vezes uma ordem acíclica ou um horizonte limitado) para que cada subproblema/estado seja resolvido uma vez.

Na prática, a DP é uma forma estruturada de implementar a ideia: “armazenar em cache (cache) o resultado para cada estado.”

Conceitos Centrais: Estados, Recorrências e Reuso

A maioria das soluções de DP é construída em torno de um pequeno conjunto de ingredientes:

1) Definição de estado

Um estado é uma descrição compacta de um subproblema. Bons estados:

  • são pequenos (para não haver estados demais),
  • são suficientes (para que a resposta ótima do subproblema dependa apenas do estado, e não do histórico completo),
  • se alinham às restrições do problema (capacidade, índice, passo de tempo, última escolha etc.).

Exemplos:

  • Mochila (knapsack): dp[i][w] = melhor valor usando os primeiros i itens com capacidade w.
  • Distância de edição (edit distance): dp[i][j] = mínimo de edições para converter os primeiros i caracteres de A nos primeiros j caracteres de B.
  • Caminhos mínimos (shortest paths): dist[v] (ou dp[k][v] em algumas formulações) = melhor distância até o vértice v.

2) Recorrência (transição)

Uma recorrência (recurrence) expressa a resposta para um estado em termos de estados menores. Formas comuns:

  • Minimização: dp[s] = min_{a in actions(s)} cost(s,a) + dp[next(s,a)]
  • Maximização: dp[s] = max_{a} reward(s,a) + dp[next(s,a)]
  • Contagem/soma: dp[s] = sum_{a} dp[next(s,a)]

A transição deve se referir a subproblemas “menores” (por índice, comprimento, tempo ou uma ordem topológica).

3) Casos-base

Estados que são triviais de resolver (prefixo vazio, capacidade zero, estado-meta, horizonte 0). Os casos-base ancoram a recorrência.

4) Ordem de avaliação

Você deve garantir que, ao computar dp[s], todos os subestados necessários já estejam computados (de baixo para cima (bottom-up)) ou que a recursão os compute conforme necessário (memoização (memoization) de cima para baixo (top-down)).

5) Reconstrução (opcional, mas comum)

Se você quer a solução, não apenas o valor ótimo, armazene ponteiros de retrocesso (backpointers) (qual escolha atingiu o min/max) para reconstruir o caminho, o alinhamento, os itens selecionados etc.

Dois Padrões Principais de DP: Memoização vs Tabulação

Memoização (DP de cima para baixo)

Você escreve uma função recursiva para a recorrência e armazena resultados em um cache.

Prós

  • Em geral, é a forma mais simples de derivar e implementar.
  • Computa apenas os estados que são de fato alcançados.

Contras

  • Sobrecarga da recursão e limites de profundidade de recursão em algumas linguagens.
  • Mais difícil de controlar a ordem de iteração; pode recomputar se o cache estiver incorreto.

Exemplo de esqueleto:

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(state):
    if is_base(state):
        return base_value(state)
    return best_over_choices(dp(next_state(state, choice)) + cost(state, choice)
                             for choice in choices(state))

Tabulação (DP de baixo para cima)

Você aloca uma tabela/array e a preenche em uma ordem que garante que os pré-requisitos já estejam disponíveis.

Prós

  • Muitas vezes mais rápida na prática (laços apertados, memória previsível).
  • Sem problemas de profundidade de recursão.
  • Mais fácil de aplicar otimizações de espaço.

Contras

  • Você pode computar muitos estados que não acabam sendo necessários.
  • É preciso escolher cuidadosamente a ordem de preenchimento.

Exemplo de esqueleto:

dp = initialize_table()
for state in states_in_valid_order():
    dp[state] = combine(dp[substate] for substate in predecessors(state))

Como Derivar uma Solução de DP de Forma Sistemática

Uma receita confiável para construir soluções de DP:

  1. Escolha o objetivo

    • Custo mínimo, recompensa máxima, número de maneiras, probabilidade etc.

  2. Identifique o que muda nos subproblemas

    • Tipicamente um índice (i), orçamento restante (w), passo de tempo (t) ou limite (l..r).

  3. Defina o estado

    • Garanta que ele capture toda a informação necessária para decisões ótimas dali em diante.

  4. Escreva a recorrência

    • Expresse o valor do estado como um min/max/soma sobre escolhas que reduzem o tamanho do problema.

  5. Prove a corretude (informalmente)

    • Argumente a subestrutura ótima: se uma solução ótima usa uma escolha, o restante deve ser ótimo para o subproblema resultante.

  6. Analise a complexidade

    • #estados × trabalho_por_estado para tempo; #estados para memória.

  7. Decida entre memoização e tabulação

    • Prefira tabulação quando há uma ordem clara e você quer desempenho; memoização quando o conjunto alcançável é esparso ou quando a recorrência é mais fácil de escrever recursivamente.

  8. Adicione reconstrução

    • Armazene decisões ou ponteiros para o pai se você precisar do plano/sequência de fato.

Complexidade: A Visão de “Espaço de Estados”

A complexidade de DP tipicamente é:

  • Tempo: ( O(|S| \cdot T) ) onde (|S|) é o número de estados e (T) é o custo para computar cada estado (muitas vezes, o número de ações/transições).
  • Espaço: ( O(|S|) ) para armazenar a tabela, às vezes redutível.

É por isso que a DP é intimamente relacionada a busca/planejamento: uma tabela de DP é efetivamente uma função de valor (value function) sobre um espaço de estados (state space).

Uma limitação comum é a maldição da dimensionalidade (curse of dimensionality): se seu estado tem muitas dimensões (por exemplo, posição × tempo × recurso1 × recurso2 × …), (|S|) pode se tornar enorme.

Exemplo Clássico 1: Caminhos Mínimos como Programação Dinâmica

Algoritmos de caminho mínimo muitas vezes podem ser vistos como DP sobre a estrutura do grafo.

Caminhos mínimos em DAG (DP pura via ordem topológica)

Se o grafo é um DAG, isto é, um grafo acíclico direcionado (directed acyclic graph, DAG), caminhos mínimos a partir de uma fonte podem ser computados processando os vértices em ordem topológica (topological order):

  • Estado: dist[v] = menor distância da fonte s até v
  • Transição: dist[v] = min_{(u->v)} dist[u] + w(u,v)
  • Ordem: a ordem topológica garante que todos os predecessores u sejam processados antes de v

Essa é uma DP “limpa” porque não há ciclos.

Bellman–Ford (DP pelo número de arestas)

O algoritmo de Bellman–Ford (Bellman–Ford) pode ser escrito como:

  • Estado: dp[k][v] = menor distância de s até v usando no máximo k arestas
  • Recorrência: [ dp[k][v] = \min\left(dp[k-1][v], \min_{(u\to v)} dp[k-1][u] + w(u,v)\right) ]
  • Resposta: dp[|V|-1][v]

Bellman–Ford está fortemente ligado a planejamento e à equação de Bellman (Bellman equation) (veja Processos de Decisão de Markov (Markov Decision Processes) e Aprendizado por Reforço (Reinforcement Learning)).

Floyd–Warshall (caminhos mínimos entre todos os pares)

O algoritmo de Floyd–Warshall (Floyd–Warshall) é uma DP clássica por tabulação:

  • Estado: dp[k][i][j] = caminho mínimo de i até j usando apenas vértices intermediários de {1..k}
  • Recorrência: [ dp[k][i][j] = \min(dp[k-1][i][j],\ dp[k-1][i][k] + dp[k-1][k][j]) ]

Uma forma otimizada em espaço usa uma única matriz 2D atualizada in-place:

def floyd_warshall(dist):
    # dist[i][j] initialized to edge weights, dist[i][i] = 0
    n = len(dist)
    for k in range(n):
        for i in range(n):
            dik = dist[i][k]
            for j in range(n):
                alt = dik + dist[k][j]
                if alt < dist[i][j]:
                    dist[i][j] = alt
    return dist

Relevância para IA: caminhos mínimos se conectam diretamente à Busca em Grafos e a métodos heurísticos como Busca A* (A* Search). Métodos de DP tendem a ser exatos e sistemáticos quando a estrutura permite.

Exemplo Clássico 2: Mochila 0/1 (Otimização com Restrição de Recursos)

O problema da mochila modela “escolher um subconjunto sob restrições”, um padrão que aparece em planejamento (alocação de recursos), escalonamento e trade-offs de seleção de modelos.

Problema

Dado n itens com valor v[i] e peso w[i], escolha um subconjunto com peso total ≤ W maximizando o valor total. Cada item pode ser escolhido no máximo uma vez.

Formulação em DP

  • Estado: dp[i][cap] = melhor valor usando itens 0..i-1 com capacidade cap
  • Base: dp[0][cap] = 0
  • Transição:
    • Não pegar o item i-1: dp[i-1][cap]
    • Pegar o item i-1 (se couber): dp[i-1][cap - w[i-1]] + v[i-1]
    • Tomar o máximo

Tabulação com otimização de espaço para 1D (iterar capacidade em ordem decrescente):

def knapsack_01(values, weights, W):
    dp = [0] * (W + 1)
    for val, wt in zip(values, weights):
        for cap in range(W, wt - 1, -1):
            dp[cap] = max(dp[cap], dp[cap - wt] + val)
    return dp[W]

Por que decrescente? Isso evita reutilizar o mesmo item várias vezes na mesma iteração, preservando a restrição 0/1.

Complexidade: (O(nW)) tempo, (O(W)) espaço.

Relevância para IA: muitos problemas combinatórios de decisão podem ser expressos com templates de DP semelhantes. Quando o (O(nW)) exato é lento demais, usam-se estratégias aproximadas ou heurísticas (relacionadas a Algoritmos de Aproximação e Algoritmos Gulosos).

Exemplo Clássico 3: Alinhamento de Sequências e Distância de Edição

Alinhamento de sequências (sequence alignment) é central em bioinformática e também aparece em IA como um template para comparar sequências, medir similaridade e decodificar modelos de sequência.

Distância de edição (distância de Levenshtein (Levenshtein distance))

Compute o número mínimo de inserções, deleções e substituições para transformar a string A em B.

  • Estado: dp[i][j] = mín. de edições para transformar A[:i] → B[:j]
  • Base:
    • dp[0][j] = j (inserir tudo)
    • dp[i][0] = i (deletar tudo)
  • Transição: [ dp[i][j] = \min\begin{cases} dp[i-1][j] + 1 & \text{(delete)}\ dp[i][j-1] + 1 & \text{(insert)}\ dp[i-1][j-1] + [A[i-1] \ne B[j-1]] & \text{(substitute/match)} \end{cases} ]

Tabulação:

def edit_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,        # delete
                dp[i][j - 1] + 1,        # insert
                dp[i - 1][j - 1] + cost  # substitute/match
            )
    return dp[n][m]

Alinhamento e retrocesso (backtracking)

Para recuperar o alinhamento, armazene qual movimento atingiu o mínimo (um ponteiro de retrocesso). Essa é a mesma ideia usada para reconstruir caminhos mínimos ou itens escolhidos na mochila.

Relevância para IA: DP para alinhamento de sequências é intimamente relacionada à decodificação em modelos probabilísticos de sequência, como Modelos Ocultos de Markov (Hidden Markov Models), em que o Algoritmo de Viterbi (Viterbi Algorithm) é essencialmente DP para a sequência de estados ocultos mais provável.

DP em Busca e Planejamento

DP não é apenas um “truque para arrays”—é uma das ferramentas matemáticas centrais por trás do planejamento sob incerteza.

Equações de Bellman (funções de valor)

Em um MDP, a função de valor ótima satisfaz um ponto fixo no estilo de DP:

[ V^(s) = \max_{a} \left( R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^(s') \right) ]

Isso é programação dinâmica sobre estados, com um máximo sobre ações e uma expectativa sobre transições estocásticas. Algoritmos como iteração de valor (value iteration) e iteração de política (policy iteration) (veja Processos de Decisão de Markov e Aprendizado por Reforço) podem ser vistos como métodos de DP.

DP vs busca heurística

  • DP tende a computar valores para muitos estados de forma sistemática (por exemplo, todos os estados em um horizonte).
  • Busca heurística (heuristic search) (por exemplo, Busca A*) tenta computar apenas o necessário para alcançar um objetivo específico, guiada por heurísticas.

No planejamento determinístico, essas perspectivas frequentemente se encontram: um planejador pode realizar uma busca de melhor-primeiro (best-first search), mas armazenar em cache valores de subproblemas já computados—misturando ideias de DP com busca.

“Formas” Comuns de DP (Padrões Úteis)

Além dos exemplos clássicos, muitos problemas se encaixam em templates recorrentes de DP:

  • DP linear (linear DP) (1D/2D sobre índices): sequências, strings, restrições simples.
  • DP por intervalo (interval DP): dp[l][r] para subarrays/substrings (por exemplo, análise sintática ótima (optimal parsing), multiplicação de cadeia de matrizes (matrix-chain multiplication)).
  • DP em árvores (tree DP): computa valores em árvores usando subproblemas pai/filho (comum em predição estruturada (structured prediction) e modelos gráficos (graphical models) em árvores).
  • DP com máscara de bits (bitmask DP): dp[mask][i] para problemas de subconjunto como o problema do caixeiro-viajante (traveling salesman problem, TSP) (exato, mas exponencial).
  • DP em grafos (DP on graphs): funciona melhor em DAGs; grafos cíclicos geralmente exigem estrutura adicional (DP limitada por arestas, relaxações de caminho mínimo ou iterações de ponto fixo (fixed-point iterations)).

Vale a pena aprender esses padrões como “blocos de construção”: muitas vezes, o principal trabalho é reconhecer qual template se aplica.

Dicas Práticas de Implementação e Armadilhas

  • Seja explícito sobre o tamanho do estado. Antes de codificar, estime o número de estados e transições. Muitas soluções de DP falham por explosão de estados “escondida”.
  • Escolha memoização quando o conjunto alcançável for esparso. Se muitos estados são irrelevantes, a DP de cima para baixo pode ser dramaticamente mais rápida.
  • Inicialize casos-base com cuidado. Erros de deslocamento de um (off-by-one errors) são o bug mais comum em tabelas de DP.
  • Use valores sentinela (sentinel values). Para minimização, inicialize com +inf; para maximização, -inf.
  • Reconstrução exige controle adicional. Armazene ponteiros para o pai (ou a escolha que atinge argmin/argmax) conforme você preenche a tabela.
  • Otimize espaço quando possível. Muitas DPs 2D podem ser reduzidas a 1D (mochila, algumas DPs de sequência) se cada linha depender apenas da linha anterior.
  • Cuidado com a profundidade de recursão. Recursão memoizada em Python pode bater limites de recursão em instâncias grandes; tabulação evita isso.

Resumo

Programação dinâmica é uma forma fundamentada de resolver problemas ao:

  • definir um estado para cada subproblema,
  • escrever uma recorrência usando subestrutura ótima,
  • computar cada estado uma vez (memoização ou tabulação),
  • e opcionalmente reconstruir uma solução ótima.

Ela se conecta diretamente a temas centrais de IA: caminhos mínimos e estrutura de grafos, tomada de decisão com restrição de recursos (problemas tipo mochila), alinhamento e decodificação de sequências, e planejamento via funções de valor no estilo de Bellman. Dominar DP significa aprender a enxergar problemas como espaços de estados com subestrutura reutilizável—uma habilidade essencial em algoritmos, busca e sistemas inteligentes de decisão.