Programação Dinâmica

Textos a ler (são curtos!):

• Projetando um Algoritmo de Prog. Dinâmica, TopCoder feature de vorthys.
• Problemas Clássicos de Prog. Dinâmica, do site de Steven Halim.
• dynamic_programming.txt, texto da Equipe de Harvard.
• week10, texto do Curso do Skiena
• Programação Dinâmica, texto do Programming Challenges.
  • Cuidado que os códigos do Skiena são muito bons para competição e nem tão enxutos!!!!!

Outras referências:

• Livros
  • The Algorithm Design Manual, Steven S. Skiena - Capítulo 3
  • Introduction to Algorithms, Cormen, Leiserson, Rivest - Capítulo 16
  • Introduction to Algorithm - A Creative Approach, Udi Manber - Seção 5.10
• Aulas em áudio de Steven Skiena
  • Programação Dinâmica: aula1 aula2

Coisas a saber:

• Programação Dinâmica como tabelamento de uma recorrência
• Tipos de P.D.: Iterativa e Memoization (ver livro do Cormen)
• Problemas diversos
  • Problema da Mochila (Knapsack Problem)
  • Distância de Edição (Edit Distance)
  • Problema da Partição (ver livro do Skiena)
  • Longest Common Subsequence (LCS)
  • Longest Increasing Subsequence (LIS)
  • Submatriz de soma máxima
  • Multiplicação em Cadeia de Matrizes (Matrix Chain Multiplication - MCM)

Exercícios a fazer, em ordem de importância:

• 10130 - SuperSale (Knapsack)
• 164 - String Computer (Edit Distance)
• 10405 - Longest Common Subsequence
• 108 - Maximum Sum
• 348 - Optimal Array Multiplication Sequence (MCM)