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 Optimizationarticle there was written dp[i−1][j]+C[k][j] i think it should bedp[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