Programação Competitiva (CC3036)

	Aula #05
	Pedro Ribeiro - DCC/FCUP

Principais conceitos abordados na aula

Conceitos de Programação Dinâmica (DP - Dynamic Programming):
- Conheço a técnica algorítmica de Programação Dinâmica e o tipo de problemas em que costuma ser aplicada
- Conheço as características de um problema para poder ser resolvido com DP: subestrutura óptima e subproblemas coincidentes
- Sei que DP pode ser aplicada "de trás para a frente" (bottom-up) ou directamente usando a forma recursiva (top-down) usando memoization para ir guardando os valores já calculados
Problemas Classicos de Programação Dinâmica:
- Conheço o problema da longest increasing subsequence (LIS), a sua formulação com DP, como pode ser resolvido de forma naive em O(N^2) ou em O(n log n) usando pesquisa binária.
- Conheço problema da longest common subsequence (LCS), a sua formulação com DP, e como pode ser visto como um caso específico de edit distance
- Conheço o problema de 0-1 knapsack e a sua formulação com DP.
- Conheço o problema do troco de moedas (coin change) e a sua formulação com DP.
- Conheço o problema de matrix chain multiplication (MCM) e a sua formulação com DP.

Slides meus de Algoritmos: o que é DP, subestrutura ótima e subproblemas coincidentes, bottom-up e top-down, LIS, LCS, Edit Distance, 0-1 Knapsack e Coin Change.
Dynamic Programming: From Novice to Advanced (TopCoder)
Dynamic programming (PEG Wiki)

[em construção - vou acrescentar aqui mais ligações]

UVA 497 - Strategic Defense Initiative (testar LIS simples e direta em tempo quadrático)
UVA 10405 - Longest Common Subsequence (testar LCS simples e direta)
SPOJ EDIST - Edit Distance (testar edit distance simples e direta)
SPOJ KNAPSACK - The Knapsack Problem (testar 0-1 knapsack simples e direto)
UVA 11137 - Ingenuous Cubrency (testar contagem de troco de moedas, simples e direta)
UVA 348 - Optimal Array Multiplication Sequence (testar MCM simples e direta)

Pedro Ribeiro - DCC/FCUP | Último update: