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 on Wiki 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.
Lights, camera, action
Breaking a problem into subproblems does not seem as obvious as there are many many ways to look at it. You can imagine this as a setting for some action. The setting can be really everything: a house, a string, a graph and so on. At each moment some actions happens. If the actions are limited we can have an overview of them and represent them somehow.
We call the representation of a setting at some moment a state. For short you can regard the whole thing as a film: more frames one after the other that are bound. The frames are the states and we need to figure out what to store and how to get from start to end. In some sense you are a director and make a film in each problem. (Of course, you have budget and deadline, but we'll get there latter) Now let's put on our first film:
An Unexpected Journey
The "world" will be New Zealand. But to be fair, we'll call it just "The Shire" and we'll represent it as 2D matrix:
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
Now let's add some inhabitants. Call them Bilbo and Gollum. Now they are placed in this world:
+--+--+--+--+
| G| | | |
+--+--+--+--+
| | |B | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
So far so good. Now we need a sensible representation of those two and other possible inhabitants. In this scenario the coordinates would be fair enough. Therefore we have B(2, 3) and G(1, 1).
1 2 3 4
+--+--+--+--+
1 | G| | | |
+--+--+--+--+
2 | | |B | |
+--+--+--+--+
3 | | | | |
+--+--+--+--+
4 | | | | |
+--+--+--+--+
Our world seems somehow still. So let's add some action. So Gandalf goes to Bilbo and says: "I'm looking for someone to share in an adventure." and the hobbit starts moving in 4 possible directions: N, S, E, W.
1 2 3 4 1 2 3 4 1 2 3 4
+--+--+--+--+ +--+--+--+--+ +--+--+--+--+
1 | G| | | | 1 | G| | | | 1 | G| | | |
+--+--+--+--+ +--+--+--+--+ +--+--+--+--+
2 | | |B | | 2 | | | | | 2 | | |B | |
+--+--+--+--+ +--+--+--+--+ +--+--+--+--+
3 | | | | | 3 | | |B | | 3 | | | | |
+--+--+--+--+ +--+--+--+--+ +--+--+--+--+
4 | | | | | 4 | | | | | 4 | | | | |
+--+--+--+--+ +--+--+--+--+ +--+--+--+--+
1 2 3 4 1 2 3 4 1 2 3 4
+--+--+--+--+ +--+--+--+--+ +--+--+--+--+
1 | G| | | | 1 | G| | | | 1 | G| | | |
+--+--+--+--+ +--+--+--+--+ +--+--+--+--+
2 | | | |B | 2 | | | | | 2 | | | | |
+--+--+--+--+ +--+--+--+--+ +--+--+--+--+
3 | | | | | 3 | | | |B | 3 | | | | |
+--+--+--+--+ +--+--+--+--+ +--+--+--+--+
4 | | | | | 4 | | | | | 4 | | | |B |
+--+--+--+--+ +--+--+--+--+ +--+--+--+--+
Now that we added frames Bilbo seems to be moving around. Now we have to add time, so a possible representation of Bilbo's journey would be:
Place[t] = (x, y)
Therefore, Biblo is at coordinates (x, y) at time stamp t. Now, having the representation of a single frame we have to bind around the frames. We know Bilbo's directions in order "SNESS" and his initial state "(2, 3)". Now we only need to find Bilbo's position at each step. We know that at each step he only moves once according to the direction indicated, so the new position can be found just by looking at the last position and the direction. Finding how to jump from a state to the other is called recurrence relation (all transitions look the same in some way, they recur).
Place[t+1] = | current_direction == 'N' = (Place[t].x - 1, Place[t].y)
| current_direction == 'S' = (Place[t].x + 1, Place[t].y)
| current_direction == 'W' = (Place[t].x, Place[t].y - 1)
| current_direction == 'E' = (Place[t].x, Place[t].y + 1)
So, that's how things work so far... Now, let's try to plot an actual problem, not just sandbox.
My precious
Conclusion
- Establish the environment (The Shire)
