Programação Dinâmica

Videoaulas

Aula 1

• Definição
• Problema da moeda
• Kadane
• Combinatória

Aula 2

• DP iterativa
• Otimização de memória
• Otimização de transição
• DP on tree

Slides

Slides da aula 1

Slides da aula 2

Códigos e Materiais

Material extra

• [Atcoder] Contest educacional de DP

Exercícios

Parte 1

• Moeda (pega ou não pega)
  • [CF] Problema da Moeda
  • [CF] Subsequência HARD
  • [CF] Tickets, transição espertinha
• Kadane
  • [Maratona UnBalloon] Kadane multiplicando um elemento
  • [CF] Kadane multiplicando um subarray
  • [CF] Subtrai k dependendo da quantidade
• Combinatória
  • [Atcoder] Degraus
  • [CF] Organizar soldados e cavaleiros
  • [OBI] Muro
  • [CF] Bicolorings (parece com Muro)
• Bitmask
  • [Maratona UnB 2020] Caixeiro Viajante
  • [CF] Bitmask e probabilidade
  • [CF] Nim game
  • [CF] Problema difícil
• Dígitos
  • [CF] Números com até 3 dígitos não nulos
  • [CF] Soma dos números com k dígitos diferentes
• Outros
  • [CF] Topzera
  • [CF] DP quadrática
  • [CF] DP de matriz
  • [NEPS] Trabalho do Papa
  • [CF] Generate a String

Parte 2

• Fixação
  • [CF] Fazer de novo de forma iterativa
  • [CF] otimização de memória
  • [Atcoder] otimização transição
• Intermediário
  • [HackerCup] otimização com minqueue
  • [CF] otimização com segtree
  • [CF] DAG
  • [NEPS] DP on tree
• Difícil
  • [CF] otimização com segtree
  • [CF] otimização jantar
  • [CF] DP on tree
  • [CF] DP on tree com otimização