Dynamic Programming
❗ Please mail If I Wrote Something Wrong ❗
Send to: jundolpop@gmail.com 📧
I’ll update the post, when I search or learn about other sources of such topic. Check my github-commit of this post, to see a history.
Source 1 - Introduction to Algorithms, Fourth Edition by MIT Press
Dynamic programming (DP) is popular for optimization problems. So, we can call DP as optimization. Those optimization contributes to suggest a best choice among a set of choices.
Divide-and-conquer method is one of the popular DP algorithms. DP is useful in the situation of that invokes several subproblems. Those subproblems are derived from the main problem. And there are sub-sub-problems, based on the ‘sub’ problems.
DP would be explained by solving principle of practical cases. I’m going to introduce several cases:
- Rod cutting - Characterise the structure of an optimal solution
- Recrusive problem - Define the value of an optiomal solution by recursing
- Compute the value, by using a bottom-up fashion.
- Construct an optimal solution from computation with information.