Exemplos de programação dinâmica

O objetivo deste artigo é listar e passar por vários problemas não clássicos de programação dinâmica, de forma a treinar um pouco diferentes padrões de aplicação deste método. Adicionalmente, introduziremos tipos de aplicações de programação dinâmica.

Exemplos iniciais

Começamos por ver alguns artigos que abordam alguns problemas em concreto e que explicam uma solução possível:

DAG

Uma estrutura menos regular onde é possível aplicar programação dinâmica é um DAG (Directed Acyclic Graph). Parece um caso muito particular, mas na verdade há muitos tipos de problemas que podem ser vistos como um DAG, por exemplo, problemas em grelhas ou outras estruturas em que os movimentos sejam unidirecionais (não se pode voltar atrás). Vejamos um artigo sobre o assunto:

Se tiverem dúvidas ou quiserem algo mais específico sobre a formulação base do método podem ver este artigo mais particular:

Bitmask

Outro tipo de programação dinâmica menos óbvia é usar como objetos que definem um subproblema um conjunto em vez de um inteiro. Para este tipo de coisa usa-se uma técnica chamada bitmasking que consiste em codificar conjuntos com inteiros tendo certos bits a 1 e a 0 para representar os elementos que estão incluídos ou não no conjunto.

* Extra

Para não ficarem com falta de tipos de programação dinâmica, aqui têm mais um conjunto de vários artigos interessantes:

Outra técnica engraçada relacionada é conhecida como delta encoding. O objetivo é calcular eficientemente um conjunto de atualizações de intervalos de valores ao deixar o trabalho necessário para o fim. Para verem melhor este método vejam um problema e a sua solução:

Aplicação

Finalmente, como não podia faltar, ficam algumas sugestões de problemas a fazer.