Week #05 | |

Pedro Ribeiro - DCC/FCUP |

**Dynamic Programming (DP) Concepts:**- I know the
**Dynamic Programming**algorithmic technique and the type of problems where it is usually applied - I know the characteristics of a problem where DP is applicable:
**optimal substructure**and**overlapping substructure** - I know that DP can be applied
**bottom-up**(finding the right order of the subproblems) or in**top-down**fashion (using more directly the recursive formula and**memoization**to store the already calculated values)

- I know the
**Classical Dynamic Programming Problems:**- I know the
**longest increasing subsequence (LIS)**problem, its DP formulation, how it can be solved more naively in O(n^2) ir in O(n log n) using binary search. - I know the
**longest common subsequence (LCS)**problem, its DP formulation, and how it can be seen as a specific case of**edit distance** - I know the
**0-1 knapsack**problem and its DP formulation - I know the
**coin change**problem and its DP formulation - I know the
**matrix chain multiplication (MCM)**and its DP formulation

- I know the

**DP concepts****My own slides:**Dynamic Programming- Dynamic Programming: From Novice to Advanced (TopCoder)
- Dynamic programming (PEG Wiki)
- Chapter 7 of Competitive Programmer's Handbook book
- Section 3.5 of the Competitive Programming book
**Classical DP Problems**- LIS - Longest Increasing Subsequence: Wikipedia | GeeksforGeeks
- LCS - Longest Common Subsequence Wikipedia | GeeksforGeeks
- ED - Edit Distance: Wikipedia | GeeksforGeeks
- 0-1 Knapsack: Wikipedia | GeeksforGeeks
- Coin Change: Wikipedia | GeeksforGeeks
- MCM - Matrix Chain Multiplication: Wikipedia | GeeksforGeeks

- [UVA 497] - Strategic Defense Initiative (testing simple LIST with quadratic time)
- [UVA 10405] - Longest Common Subsequence (testing simple and direct LCS)
- [SPOJ EDIST] - Edit Distance (testing simple and direct edit distance)
- [SPOJ KNAPSACK] - The Knapsack Problem (testing simple and direct 0-1)
- [UVA 11137] - Ingenuous Cubrency (testing simple and direct coin change)
- [UVA 348] - Optimal Array Multiplication Sequence (testing simple and direct MCM)

Pedro Ribeiro - DCC/FCUP |
**Último update:**