This Blog is Just the List of Problems for Dynamic Programming Optimizations.Before start read This blog.
1.Knuth Optimization
Read This article before solving Knuth optimization problems.
Problem 1 Problem 2 Problem 3 ( C ) Problem 4 Problem 5 Problem 6
2. Divide and Conquer Optimization
Read This article before solving Divide and Conquer Optimization problems
Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Problem 7 Problem 8 Problem 9 Problem 10 Problem 11
3. Convex Hull Trick Technique(CHT)
Read This article before solving problem based on CHT.
Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Problem 7 Problem 8 Problem 9 Problem 10 Problem 11
Note:- Some problems from Divide and conquer optimization section can also be solved using CHT.
Please, share your knowledge and links on the topic.
Link to Problem 1 and Problem 4 on Divide and Conquer Opt point to the same problem
Edited :- Thank You .
two more problems for CHT :
377E , 91E
Added. Thank You.
I think in Divide and Conquer Optimization article there was written dp[i−1][j]+C[k][j] i think it should be
dp[i−1][k]+C[k][j]?
Yes You are correct. The fifth line of first paragraph there should be dp[i−1][k]+C[k][j].
Another one: Ciel and Gondolas
Look Problem 5. Which was same as you given.
Nice Collections , Liked it.
Thanks.
Thanks a lot bro . Was searching for something like this . :)
Another problem that can be solved using D&C: ARC 067 problem F
Added. Thank You.
One more problem of Divide and Conquer
http://mirror.codeforces.com/problemset/problem/834/D
POJ 1741 is solvable with Tree/Sibling Dp + Divide and Conquer.
If it suits, it can be added.
Added. Thank You.
FYI, it's not the divide and conquer optimization. Should be removed from the list.
Added. Thank You.
There is also a very cool technique to optimize DP. I have seen it in a Radewoosh comment here and in a recent CSAcademy contest here.
Auto comment: topic has been updated by khatribiru (previous revision, new revision, compare).
Fresh problem. Can be solved with CHT.
Thanks
From Codechef Long Challenge July19 Can be solved using CHT