Main learning outcomes for this class
- 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)
- 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
Study Material
Main references
- DP concepts
- Classical DP Problems
Initiation/Reinforcement Problems
Pedro Ribeiro - DCC/FCUP | Last update:
