Target Audience : If you are not able to come up with the $$$O(n^2)$$$ algorithm in 5 minutes, and the $$$O(n)$$$ algorithm in additional 5 minutes, this tutorial is for you. If you are a beginner to Dynamic Programming on Prefix, this 1D DP problem is a good starting point for you to learn the technique. This tutorial assumes that you already have some experience with 1D DP.
I came across a simple yet elegant problem, which might be trivial to some but a good learning experience for others. So I created a blog that talks about how to optimize DP transitions by switching from Pull DP to Push DP.
You can submit your $$$O(n^2)$$$ and $$$O(n)$$$ solution here : https://mirror.codeforces.com/group/7Dn3ObOpau/contest/517981
https://cfstep.com/training/tutorials/dp/push-dp-vs-pull-dp/
If you have an alternate solution for any of these problems, do let me know in the comments.
If you have more practice problems on this concept, please share them in the comments below and I'll add them to the practice contest.
Comments (0)
