Introdução à programação dinâmica

Neste artigo iremos explorar um tema conhecido como "Programação Dinâmica". A ideia será explorar a estrutura de um problema de forma a não calcular valores que já tenham sido calculados.

Este artigo terá essencialmente duas partes: uma em que discutimos a ideia base deste conceito; uma em que visitamos um conjunto de problemas clássicos de programação dinâmica.

Introdução

Começamos com uma leitura interessante e concisa:

Se quiserem mais uma introdução podem consultar outro artigo que inclui mais alguns exemplos.

Problemas clássicos

Passamos agora a um overview de vários problemas clássicos deste tema.

Longest Increasing Subsequence

Neste problema é suposto, como o nome indica, calcular a maior subsequência crescente de uma sequência de inteiros. É um problema muito simples mas ao mesmo tempo interessante com muitas variantes possíveis. Um exemplo é o problema maior subsequência decrescente, que é uma adaptação trivial do problema. Um exemplo não trivial é do maior subsequência bitónica, ou seja, que é estritamente crescente até um certo ponto e a partir dai é estritamente decrescente. Mas afinal como se resolve?

O algoritmo visto tem complexidade temporal $O(N^2)$, mas na verdade conseguimos fazer muito melhor, eis um artigo que mostra uma forma de resolver este problema em $O(N\log(N))$:

Uma nota curiosa, um problema deste estilo saiu numa prova de Seleção das ONI, nomeadamente o A de 2015, Tragédia Grega. Embora a solução seja um pouco mais complicada do que as técnicas apresentadas aqui, é um bom exemplo de como este problema é versátil.

Coin Change

O problema do troco das moedas pergunta para um dado valor $V$ e um conjunto de valores de $N$ moedas, qual o mínimo número de moedas necessário para fazer a quantia $V$. Vejamos como o resolver:

0-1 Knapsack

Dado um conjunto de itens, cada um com um peso e valor associado, é pedido para determinar o conjunto de itens com maior soma de valores, sendo que o peso total desses itens não pode exceder um determinado inteiro $W$. Uma possível solução:

2D Maximum Sum

Dada uma matriz de inteiros, é pedido para calcular o sub-retângulo cuja soma seja a maior possível. Veremos como fazê-lo.

Na próxima secção veremos um método que nos permite otimizar a solução vista.

* 1D Maximum Sum

Este problema, também conhecido como maximum subarray problem, pede para calcular a subsequência contígua de uma dada sequência de inteiros cuja soma seja a maior possível. Vejamos que é possível fazê-lo em $O(N)$ com um algoritmo conhecido por "algoritmo de Kadane".

Agora fica o desafio: como usar este algoritmo para tornar a solução do problema a duas dimensões de $O(N^4)$ para $O(N^3)$, node $N$ é a dimensão da matriz do input.

Aplicações

Finalmente, veremos alguns problemas para treinarem.

Conclusão

Há muitos outros exemplos clássicos que podíamos falar, por exemplo o Edit Distance ou o Longest Common Subsequence, mas com estes exemplos já têm uma boa ideia do que é a programação dinâmica e já podem começar a experimentar problemas mais complicados.