What is dp?
A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states. A sub-solution of the problem is constructed from previously found ones.
What does a state stand for?
It’s a way to describe a situation, a sub-solution for the problem.
As described above we must first find how to define a "state" which represents a sub-problem and thus we have to find a solution for it. Note that in most cases the states rely on lower states and are independent from greater states.
Examples
- Beginner => LC 322 Coin Change
- Elementary => LC 300 LIC
- Intermediate => Similar to LC 64 Minimum Path Sum
- Upper Intermediate => BUY AND SELL STOCK PROBLEMS
- Advanced
BackPack
https://segmentfault.com/a/1190000006325321
Tips
- when you are doing the loop, think about which index is for dp[] array, and which is for the original array