Módulo Programação Dinâmica

Este módulo é um dos mais importantes que iremos ver. Não porque o seu conteúdo seja particularmente difícil ou recorrente em problemas, mas os conceitos que podem aprender são aplicados em imensos outros tópicos de problemas. Adicionalmente, assim como aconteceu com a pesquisa binária, há vários problemas que usam como uma primitiva ou subparte do problema calcular ou resolver alguma coisa usando programação dinâmica.

Este módulo está dividido por 3 artigos. No primeiro introduz-se o método e discutem-se os exemplos clássicos que são representativos da programação dinâmica. Seguimos com um módulo que apresenta uma vista geral de vários problemas, métodos e padrões para aplicar programação dinâmica. Finalmente, vemos um exemplo mais particular, e que daria um módulo só por si, como podemos pensar em jogos combinatórios e usar programação dinâmica para resolver vários deles.

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

Neste artigo introduzimos o conceito e vemos os exemplos clássicos.

Artigo: Exemplos de programação dinâmica

Aqui vemos vários exemplos práticos assim como aplicações gerais do método.

Artigo: Jogos combinatórios

Uma breve introdução guarnecida de exemplos práticos aos conceitos de jogos combinatórios.

Agora que já dominam programação dinâmica, devem-se lembrar dos inúmeros problemas das ONI onde dava muito jeito aplicar este tipo de coisa. Depois de terem passado por pesquisa binária, o problema B da final deste ano deve ser agora ainda mais claro, No Fundo do Mar, visto que a sua solução passa por uma conjunção de ambas as técnicas.

Problemas de consolidação

Este conjunto de problemas é constituído por alguns problemas extra um pouco mais difíceis, mas que resumem bem a maioria dos tópicos dos artigos.

Nota: A fonte dos problemas representa a plataforma de submissão (todos são submetiveis) e não o concurso onde apareceu.