INGIniousDynamic Programming (DP for short) is a fundamental technique in the development of efficient algorithms.
Mastering this technique will allow you to solve a lot of problem that seem intractable at first and is a necessary condition in order to be a successful algorithmist.
We will start by studying the Knapsack problem and use it to illustrate several aspects of DP, namely:
- Top-down DP vs Bottom-up DP
- The DP state graph
- Reconstructing the solution
- DP memory reduction
- DP state reformulation