Lançado · em melhoria
Algorithm
A programação dinâmica guarda e reutiliza soluções de subproblemas sobrepostos, transformando buscas exponenciais em algoritmos eficientes com tabelas.
A programação dinâmica (DP) é uma técnica de projeto de algoritmos que divide um problema em subproblemas menores, resolve cada um apenas uma vez, guarda a resposta e a reutiliza sempre que o mesmo subproblema aparece de novo. Formalizada por Richard Bellman nos anos 1950, ela se aplica quando os subproblemas se sobrepõem e quando a solução ótima pode ser montada a partir das soluções ótimas dos subproblemas.
Muitos problemas que levam tempo exponencial com recursão simples ou força bruta passam a ser resolvidos em tempo proporcional ao número de estados. A programação dinâmica está por trás das ferramentas de diff, da distância de edição nos corretores ortográficos, do alinhamento de sequências de DNA, do algoritmo de Viterbi no reconhecimento de voz e da escolha da ordem dos joins nos otimizadores de bancos de dados. Também é um dos temas mais cobrados em entrevistas técnicas.
Para começar, use Fibonacci para entender a diferença entre memoização (de cima para baixo) e tabulação (de baixo para cima) e, em seguida, resolva os clássicos: troco com o mínimo de moedas, mochila 0/1, maior subsequência crescente, maior subsequência comum e distância de edição. Em cada problema, defina primeiro o estado, a recorrência, os casos base e a ordem de cálculo, confira a recorrência preenchendo uma pequena tabela à mão e só depois escreva o código.
Quando o mesmo subproblema aparece várias vezes, ele é calculado uma única vez e armazenado, e o trabalho repetido vira uma consulta à tabela.
A solução ótima precisa ser construída a partir de soluções ótimas dos subproblemas; é essa propriedade que justifica a recorrência.
A implementação pode ser de cima para baixo, com um cache na recursão (functools.cache), ou de baixo para cima, preenchendo uma tabela com laços.
O estado guarda apenas os parâmetros que determinam a resposta, e arrays rolantes mantêm na memória só as linhas necessárias.
knapsack resolve o problema da mochila 0/1 de baixo para cima com uma única linha, percorrendo as capacidades da maior para a menor para que cada item seja usado no máximo uma vez. lcs calcula o comprimento da maior subsequência comum de cima para baixo, com memoização via functools.cache. Ao executar python dynamic_programming.py, são impressos 9 e 4.
dynamic_programming.py
from functools import cache
def knapsack(weights, values, capacity):
"""0/1 knapsack: best total value within capacity (bottom-up, one row)."""
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
for c in range(capacity, w - 1, -1): # high to low: each item used at most once
best[c] = max(best[c], best[c - w] + v)
return best[capacity]
def lcs(a, b):
"""Length of the longest common subsequence (top-down, memoized)."""
@cache
def solve(i, j):
if i == len(a) or j == len(b):
return 0
if a[i] == b[j]:
return 1 + solve(i + 1, j + 1)
return max(solve(i + 1, j), solve(i, j + 1))
return solve(0, 0)
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)) # 9
print(lcs("ABCBDAB", "BDCABA")) # 4
python dynamic_programming.pySeis capítulos que levam você da instalação aos conceitos essenciais de Programação dinâmica.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Programação dinâmica.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.