Some of you made the mistake of demanding an article on one of my favorite topics.
Cutting to the chase
As a young programmer, I heard about DP from contests. Searched it on Google. Urban Dictionary gave unsatisfying results. Then I searched for Dynamic Programming and found that:
"dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions — ideally, using a memory-based data structure"
Sounds pretty general, huh? Let's get there step by step.
An Unexpected Journey
Breaking a problem into subproblems does not seem as obvious as there are many many ways to look at it.
- Establish the environment (The Shire)