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 {{ transform.ToMath “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