Lecture on advanced dynamic programming
June 21, 2025
I gave this lecture at a training camp for luxembourgish students going to various international competitions.
We discuss the longest decreasing subsequence problem again, going over the O(n^2) solution again, and introducing the O(n log n) algorithm as an improvement.
Then we spend the rest of the workshop giving examples of various problems involving DP.
You can find the slides here: Advanced DP