Programação dinâmica não é magia negra

• Mesmo problemas com muitos casos especiais, como o Advent of Code 2023 Day 12, podem ser tratados com programação dinâmica quando se identifica uma estrutura que resolve repetidamente os mesmos subproblemas
• A ideia central é dividir o problema com recursão, reduzir cálculos duplicados com memoização e então migrar para um cálculo iterativo que preenche os valores necessários na ordem de dependência
• O exemplo de Fibonacci mostra que a recursão ingênua avalia f(1) repetidamente, mas, usando cache, basta avaliar apenas n + 1 valores, de f(0) a f(n)
• A distância de Levenshtein e o Advent of Code Day 12 mostram o processo de usar índices de estado, como comprimento de strings e índice de regras, como chaves de cache para transformar chamadas recursivas em preenchimento de arrays
• Ao dominar programação dinâmica, além de melhorar desempenho, você passa a enxergar os estados intermediários e relações de dependência do algoritmo, ficando mais fácil encontrar oportunidades de otimização de memória

---

O nome é confuso, mas a ideia é simples

• O nome “dynamic programming” não tem relação direta com significados modernos como “estilo de programação” ou “tipagem dinâmica”
• A essência é uma forma de projetar algoritmos que divide um problema em problemas menores semelhantes e reutiliza seus resultados
• Há uma nota editorial acrescentando que a expressão faz sentido quando se considera “programming” em seu significado histórico
• O ponto de partida costuma ser uma forma que decompõe o problema em problemas menores, como uma função recursiva
• Quando o mesmo subproblema aparece várias vezes, surge naturalmente a necessidade de cache para armazenar e reutilizar resultados

Cache e transformação em iteração com Fibonacci

• A função de Fibonacci é definida como f(n) = f(n - 1) + f(n - 2), e uma implementação recursiva ingênua calcula os mesmos valores repetidamente
• Como f(1) é um valor que de fato é somado ao resultado final, à medida que f(n) cresce, o número de avaliações da recursão ingênua também aumenta rapidamente
• Ao usar cache ou memoização dos resultados, não é necessário recalcular f(4), f(3) e f(2) já calculados
• Nesse método, avaliam-se apenas 7 valores no total, de f(0) a f(6); em geral, isso é reduzido para n + 1 avaliações
• Indo um passo além, se preenchermos os valores necessários em ordem a partir de f(0) e f(1), as chamadas recursivas desaparecem
  • F[2] = F[1] + F[0]
  • F[3] = F[2] + F[1]
  • Da mesma forma, calcula-se até F[6] = 8
• Em Fibonacci, nem mesmo o array inteiro é necessário: basta manter o valor anterior e o valor antes dele
• Esse fluxo mostra um caminho sistemático que parte da definição matemática e chega a uma implementação iterativa

Expandindo para o exemplo de distância de edição

• A distância de edição entre duas strings é o número mínimo de edições necessárias para transformar uma string em outra
• O problema muda conforme os tipos de edição permitidos
  • Se apenas substituição de caracteres for permitida, é a Hamming distance
  • Se inserção e remoção também forem permitidas, é a Levenshtein distance
• A distância de Levenshtein pode ser dividida em problemas menores com base no último caractere de duas strings A e B
  • Se os últimos caracteres forem iguais, ignoram-se os dois caracteres e usa-se a distância das strings restantes
  • Se os últimos caracteres forem diferentes, escolhe-se o menor custo entre substituição, remoção e inserção
  • Se A estiver vazia, é preciso inserir todos os caracteres de B, então o custo é b
  • Se B estiver vazia, é preciso remover todos os caracteres de A, então o custo é a
• Ao transpor essa definição diretamente para uma recursão em Python, ela fica muito lenta para strings longas e strings com muitas diferenças
• Se Fibonacci crescia em aproximadamente dois ramos a cada nível da árvore de chamadas, esta recursão pode crescer em três ramos, dependendo do caso
• Ao adicionar functools.cache do Python, é possível reutilizar os resultados de cálculo das mesmas combinações de substrings
• Uma implementação melhor não cria novas strings o tempo todo; ela passa apenas as strings originais A e B e os comprimentos das substrings a e b
• Na etapa final, cria-se diretamente um array bidimensional cache e ele é preenchido em ordem de modo que cache[a][b] = levenstein(A[:a], B[:b])
• A versão iterativa percorre a e b de 0 até o comprimento das strings, consultando valores da linha anterior e da coluna anterior que já foram preenchidos

Aplicando ao Advent of Code 2023 Day 12

• O problema de 12 de dezembro de 2023 do Advent of Code consiste em resolver um nonogram unidimensional
• Uma entrada de exemplo tem a forma .??..??...?##. 1,1,3, em que ? pode ser . ou #
• Uma abordagem por força bruta usa backtracking, mas, se houver n pontos de interrogação, é preciso avaliar 2^n candidatos, crescendo exponencialmente
• Aparece uma estrutura em que os mesmos subproblemas se repetem
  • ..#..??...?##. (1),1,3
  • .#...??...?##. (1),1,3
  • Ao descartar a parte inicial já processada, eles se tornam problemas quase iguais, como .??...?##. 1,3 e ..??...?##. 1,3
• A função básica de backtracking recebe conditions e rules e calcula o número de arranjos possíveis
  • Se não restarem regras, verifica se ainda há # nas condições restantes
  • Se não restarem condições, verifica se ainda há regras restantes
  • Se o caractere atual for . ou ?, avança uma posição e calcula
  • Se o caractere atual for # ou ?, verifica o tamanho da próxima regra e a condição do separador, depois passa para o próximo estado
• Em Python, basta adicionar @cache para aplicar memoização
• Para transformar em programação dinâmica, em vez de recortar a string e as regras a cada chamada, usa-se o deslocamento da string i e o deslocamento das regras j como estado
• Depois, cria-se diretamente cache[i][j] e substitui-se a recursão por cálculo iterativo preenchendo os índices em ordem inversa
• Um exemplo de implementação em Rust é fornecido no link Rust implementation dentro do artigo

O que fica visível ao preencher o cache diretamente

• A versão com programação dinâmica do Advent of Code Day 12 pode parecer mais lenta do que a versão com memoização
• Essa diferença provavelmente se deve a uma implementação em Python não otimizada
• Ao construir o cache diretamente, fica mais claro quais valores são realmente necessários
• No problema do Day 12, a versão com programação dinâmica permite confirmar que só a coluna anterior é necessária
• Portanto, é possível trocar o array bidimensional por dois arrays unidimensionais, representando a coluna anterior e a coluna atual

Problemas para praticar e conclusão

• Programação dinâmica não é trivial, mas também não é uma técnica inacessível para a maioria dos programadores
• Ao entender como dividir um problema em problemas menores, em muitas situações a memoização por si só já pode melhorar muito uma implementação ingênua
• Com mais prática, é possível compreender uma família de algoritmos, avaliar melhor os trade-offs e encontrar otimizações adicionais
• Os seguintes problemas são sugeridos para prática
  • longest common subsequence
  • line wrap
  • subset sum
  • partition
  • knapsack
• Depois de implementar, não se deve esquecer de fazer benchmarks e profiling

[GN⁺]

Opiniões do Hacker News

• Gostei do ponto em que o texto destaca que algoritmos de programação dinâmica são apenas uma forma inteligente de cachear recursão. Pela minha experiência, encontrar primeiro uma solução recursiva é o melhor ponto de partida para chegar a uma solução de programação dinâmica; uma vez encontrada, a memoização é fácil e pode trazer um grande ganho de velocidade.
  Às vezes ela é até mais rápida do que a programação dinâmica bottom-up, porque calcula apenas as soluções realmente necessárias. O ponto central é que tudo bem haver muitos subproblemas na árvore de chamadas, mas o número de subproblemas diferentes precisa ser relativamente pequeno. Não há motivo para cachear um resultado que só é necessário uma vez, e a dificuldade está em dividir o problema original em um número suficientemente pequeno de subproblemas distintos.

  • A parte de que é preciso haver relativamente poucos subproblemas diferentes é essencial. Se o algoritmo como um todo é recursivo ou iterativo é secundário, e a programação dinâmica normalmente tende a aparecer com frequência em algoritmos recursivos.
  • A explicação de que “programação dinâmica é uma forma de cachear recursão” foi o que fez tudo clicar para mim. Na faculdade, talvez porque a programação procedural fosse dominante na época, os exemplos dos livros de preenchimento de tabelas bottom-up pareciam mágica.
    Na prática, como a eliminação de chamadas de cauda nem sempre é aplicada, faz sentido fazer assim, mas eu gostaria de ter aprendido primeiro pela perspectiva mais intuitiva de cache recursivo top-down.
  • Quando aprendi pela primeira vez, pensei que, se era um recurso tão sofisticado, talvez devesse se chamar memoização em array ou memoização da pilha de chamadas. Acho que o nome “programação dinâmica” deveria ter sido reservado para algo melhor.
  • Acho que enxergar programação dinâmica simplesmente como recursão memoizada é um equívoco bastante difundido. Se você aprende assim, fica muito difícil entender problemas de programação dinâmica do tipo preencher um array bidimensional.
    Por exemplo, na série “Best Time to Buy and Sell Stock” do LeetCode, em problemas como https://leetcode.com/problems/best-time-to-buy-and-sell-stoc..., não parece muito mais natural preencher um array? Nunca tentei resolver de forma recursiva e nem sei bem se existe uma solução recursiva natural.
    O link acima é o III, mas para quem está começando, começar pelo primeiro problema https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... é uma boa introdução à programação dinâmica.
  • Dizer que “programação dinâmica é só cache/memoização” é parecido com dizer que “investir é só comprar algo e vender depois”. Tecnicamente pode até estar mais ou menos correto, mas deixa escapar tanto da complexidade e dificuldade do tema que pode soar mais ridículo do que perspicaz.

• A origem do nome “programação dinâmica” vem de seu inventor, Richard Bellman. Em 1950, na RAND, ele procurava um nome para processos de decisão em múltiplos estágios; na época, o secretário de Defesa Wilson detestava patologicamente a palavra “pesquisa”, e “matemática” era algo que devia ser evitado ainda mais.
  Bellman precisava de um nome que ocultasse de Wilson e da Força Aérea o fato de que, dentro da RAND, ele estava na verdade fazendo matemática. Então escolheu “programming”, porque tratava de planejamento, tomada de decisão e pensamento, mas “planning” não era uma boa opção por vários motivos; e acrescentou “dynamic”, que tem um significado preciso na física clássica, para capturar a ideia de múltiplos estágios e variação ao longo do tempo.
  Ele também gostou do fato de que “dynamic”, como adjetivo, é difícil de usar com sentido negativo, e por ser um nome ao qual até um congressista teria dificuldade de se opor, passou a usar dynamic programming como um termo abrangente para suas atividades.
  Fonte: https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/in...

• Gosto de como este texto primeiro expõe o problema recursivamente, depois adiciona cache de forma gradual e, por fim, reduz o tamanho do cache apenas ao necessário.
  Muitas vezes tentei ir direto para uma solução de programação dinâmica e fiquei travado, ou precisei forçar demais para fazê-la funcionar. Daqui em diante, pretendo me obrigar a seguir as etapas em ordem.

  • Pela minha experiência, ensinar programação dinâmica diretamente faz com que ela pareça um quebra-cabeça. Explicar passo a passo por que usar uma tabela e conectar esse conceito a cache torna tudo muito mais fácil de entender.

• Uma aplicação interessante de programação dinâmica é o alinhamento par a par de sequências de nucleotídeos/proteínas.
  https://en.wikipedia.org/wiki/Sequence_alignment
  https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algor...
  https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...

  • Considero esses algoritmos alguns dos mais importantes em bioinformática/biologia. Eles têm uma gama de aplicações muito ampla.

• Tive um professor de algoritmos muito bom, que havia estudado na UCLA. A aula sobre programação dinâmica foi excelente: ele começava com um problema cuja solução simples tinha complexidade de tempo exponencial, depois dividia o problema em problemas menores para reduzir a complexidade a um nível polinomial e, por fim, aplicava memoização para derrubá-la para linear
  Seria bom lembrar quais eram os problemas usados na época

  • Entre os candidatos estão a sequência de Fibonacci, o problema do troco de moedas, o problema da mochila 0/1, multiplicação em cadeia de matrizes, maior subsequência comum, maior subsequência crescente, problemas de caminho mínimo como Floyd-Warshall e distância de edição (distância de Levenshtein)
    Todos são exemplos clássicos em que a solução ingênua é ineficiente e a programação dinâmica traz uma grande melhoria
  • Também deixei alguns no texto, e são problemas comuns em aulas ou exercícios práticos. Por exemplo, maior subsequência comum, maior substring comum, line warp, soma de subconjuntos, partição e problema da mochila
    Para mais exemplos, veja https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms...
  • Além dos problemas citados por outras pessoas, também poderia ter sido um problema de escalonamento. Por exemplo, otimizar, por algum critério como throughput, N eventos que se sobrepõem no tempo, uma grade de aulas ou processos de CPU
    Pelo que sei, se você adiciona restrições especiais como “estas duas disciplinas precisam ser cursadas juntas”, isso fica muito mais complexo e difícil de tratar do que a programação dinâmica comum
  • Era alguém que estudou na UCLA com Kang?

• Como o site original parece não estar aguentando o tráfego, deixo um link arquivado
  https://web.archive.org/web/20240114111200/https://qsantos.f...

• Graças à programação dinâmica, foi possível calcular o número de posições legais no Go, e o valor era um número de 171 dígitos
  A abordagem ingênua leva tempo 3^(n^2), pois examina todas as posições possíveis em um tabuleiro de Go n×n, mas a programação dinâmica basicamente remove uma dimensão e reduz a complexidade de tempo para O(n^5 * 5.4^n) e a complexidade de espaço para O(n * 5.4^n)
  https://tromp.github.io/go/legal.html
  https://tromp.github.io/go/gostate.pdf

• O nome “Dynamic Programming” pode parecer estranho porque, aqui, programming não se refere à área de programação. Nesse caso, o sentido é mais próximo de otimização, como em programação linear
  A programação dinâmica pode ser vista como um método para resolver problemas de decisão em tempo discreto, isto é, escolher a sequência ótima {a_t} que maximiza \sum_t u_t(a_t) sob restrições. Ela define a função de valor V* como V*(t) = max_{a_t}{ u_t(a_t) + V*(t-1) }, reduzindo bastante a dimensionalidade do problema de otimização

  • Na verdade, a origem oficial do nome https://en.wikipedia.org/wiki/Dynamic_programming#History é bem engraçada. Bellman disse que gostava de “dynamic” porque era um adjetivo impossível de usar em sentido negativo, e considerava que era um nome ao qual nem um congressista poderia se opor
  • Quando outras pessoas usam a expressão “programação dinâmica”, às vezes isso soa como uma tentativa de parecer inteligente. Na prática, elas só estão usando uma abordagem natural e intuitiva de perceber que o problema pode ser dividido em subproblemas cada vez menores, mas falam como se tivessem “usado” alguma técnica especial
  • É interessante notar que, antigamente, fazer cálculos de coisas como problemas de otimização dominava muito mais a ideia do que se podia fazer com computadores. Hoje, a maior parte é armazenamento e consulta de dados e networking; mesmo quando há cálculos no meio, a sensação é que eles costumam estar bem encapsulados
  • A palavra “otimização” causa uma confusão parecida. Certa vez fiz uma disciplina de ciência da computação chamada “optimization” esperando algo completamente diferente
  • Indo ainda mais longe, “programming” descreve esse conceito com precisão. O que hoje chamamos de “programação” é, na verdade, escrita de código, e pode ser dividido em ramos como programação funcional, declarativa e procedural. Há muito mais coisa sob esse guarda-chuva

• Ao ouvir “programação dinâmica”, seria errado pensar simplesmente em memoização? A parte que falta talvez seja decompor o problema de forma inteligente para poder usar memoização

  • Memoização é uma técnica mais geral. Muitas vezes é apenas cachear um resultado já calculado para o caso de ele ser necessário novamente mais tarde
    Programação dinâmica está mais próxima de uma memoização sistemática. Ela resolve subproblemas cada vez maiores até chegar à solução do problema inteiro. O termo “algoritmo indutivo” também combina até certo ponto, porque um algoritmo típico de programação dinâmica é, na prática, parecido com uma prova por indução matemática. Infelizmente, esse termo já tem outros significados
  • Eu ensino programação dinâmica exatamente assim. Primeiro, resolvo de forma recursiva; depois, adiciono memoização. Isso é chamado de top-down
    Depois, ao observar que há overhead na recursão e na memoização, se você construir a tabela de baixo para cima e eliminar as chamadas recursivas, isso vira programação dinâmica
  • Na minha abordagem, a memoização é a etapa 2 de 3 da programação dinâmica. A etapa 1 é encontrar um algoritmo recursivo; a etapa 2 é a memoização; a etapa 3 é transformá-lo em iterativo/bottom-up e, se possível, fazer uma 3b com otimização de espaço
    A etapa 3 é a parte mais característica da programação dinâmica, mas acho que, mesmo parando na etapa 2, ainda dá para chamar de programação dinâmica. Só não será tão eficiente quanto poderia. Dito de outra forma, memoização é caching; a etapa 3 é perguntar se existe uma forma de preencher esse cache antecipadamente
  • Também há soluções de programação dinâmica que não são baseadas em memoização. Por exemplo, no problema de encontrar a substring comum mais longa de duas strings, você só precisa uma vez das células à esquerda e acima na tabela, então a memoização não ajuda muito
    Em geral, se os subproblemas se sobrepõem muito e a solução ótima dos subproblemas precisa fazer parte da solução ótima global, há uma oportunidade para programação dinâmica. Dizer que apenas memoização é programação dinâmica é parecido com dizer que apenas uma tabela hash é um tipo abstrato de dados
  • Pelo meu critério, pensar assim está errado. Para começar, há o contraexemplo óbvio de que memoização pode ser usada fora da programação dinâmica. Por outro lado, a maioria dos algoritmos de programação dinâmica pode ser implementada salvando resultados em uma tabela e depois procurando a melhor resposta nessa tabela
    Memoização é, basicamente, uma estratégia para tornar um algoritmo mais rápido

• Foi divertido terminar o Advent of Code deste ano. Ficou claro que o dia 1, especialmente a parte 2, foi muito mais difícil do que em anos anteriores, e escrevi sobre isso em https://blog.singleton.io/posts/2024-01-02-advent-of-code-20..., mas comparar apenas as estatísticas atuais de 2022 com as estatísticas atuais de 2023 não deixa isso evidente. Isso porque as pessoas tiveram um ano a mais para resolver os puzzles de 2022
  Ao buscar as estatísticas de 2022 em 14 de janeiro de 2023 https://web.archive.org/web/20230114172513/https://adventofc..., a diferença ficou bem grande. Ao plotar as estatísticas de conclusão da parte 2 https://blog.singleton.io/static/imgs-aoc23/completion.png, o tamanho do grupo inicial no dia 1 era parecido, mas 2023 parece claramente mais difícil que 2022 até o dia 15
  A proporção de pessoas que resolveram a parte 1 mas não conseguiram resolver a parte 2 https://blog.singleton.io/static/imgs-aoc23/ratios.png também foi muito maior em muitos dias de 2023, sugerindo especialmente que o dia 5, o dia 10, o dia 12 e a parte 2 do dia 22 foram difíceis

  • O Advent of Code dos primeiros tempos era divertido, e dava para se virar sem técnicas grandiosas até antes da reta final. Depois ficou mais difícil e menos divertido, então desisti e não voltei mais a mexer nele
  • Não avancei muito no Advent of Code deste ano por falta de tempo, mas talvez eu volte a tentar depois
    Ainda assim, fiquei surpreso com o quanto a parte 2 do dia 5 foi difícil. Consegui resolver sem desistir, mas achei que talvez tivesse deixado passar algo óbvio e resolvido de um jeito exageradamente complicado; foi um alívio saber que era mesmo um problema um pouco desafiador
  • É só uma experiência pessoal, e talvez tenha influenciado o fato de eu ter tentado em uma linguagem diferente da que uso normalmente, mas acho que a parte 2 do dia 1 não era tanto difícil quanto tinha uma descrição inadequada do problema
    Foram dados como exemplos two1nine, eightwothree, abcone2threexyz, xtwone3four, 4nineeightseven2, zoneight234, 7pqrstsixteen, mas faltou um exemplo essencial como oneight. Sem um exemplo assim, fica difícil descobrir exatamente como os valores deveriam ser substituídos
  • Somando a esta discussão, tenho um script que mostra o progresso por dia. As duas últimas colunas revelam o quanto 2023 foi cruel em comparação com 2022, especialmente no começo
    Em 2022, a maioria continuou participando nos primeiros dias, a taxa de retenção passou de 80% em muitos dias, e quase todos resolveram as duas partes. Em contraste, no dia 1 de 2023, entre as pessoas que resolveram a parte 1, apenas 76% resolveram também a parte 2, e muita gente desistiu nos dias 3 e 5
    Curiosamente, os últimos dias não foram tão baixos, o que pode ser explicado pelo fato de o Advent of Code de 2023 ser mais recente que o de 2022. Minha interpretação é que esse grupo é formado por pessoas que, independentemente da dificuldade, superam todos os desafios até certo ponto, enquanto muitas outras param quando sentem que está tomando tempo demais