DP

Правка en8, от DanAlex, 2016-02-06 04:41:41

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 |  |  |  |  |
  +--+--+--+--+

Conclusion

  1. Establish the environment (The Shire)
Теги dp, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en29 Английский DanAlex 2017-08-10 00:20:16 1 Tiny change: '_\n\n[cut]\n\n### Cu' -> '_\n\n[cut].\n\n### Cu'
en28 Английский DanAlex 2017-08-08 03:26:57 9 Tiny change: 'blic._\n\n### Cu' -> 'blic._\n\n[cut]\n\n### Cu'
en27 Английский DanAlex 2016-03-21 03:46:03 9 Tiny change: ' by step. [cut]\n\n\n### Ligh' -> ' by step. \n### Ligh'
en26 Английский DanAlex 2016-03-21 03:45:25 2 Tiny change: ' [cut]\n\n### Li' -> ' [cut]\n\n\n### Li'
en25 Английский DanAlex 2016-02-07 15:37:06 6 Tiny change: 'p by step.\n\n### Li' -> 'p by step. [cut]\n\n### Li'
en24 Английский DanAlex 2016-02-07 15:35:10 0 Added tags.
en23 Английский DanAlex 2016-02-06 17:53:59 2 Tiny change: '\n#### Stare expansio' -> '\n#### State expansio'
en22 Английский DanAlex 2016-02-06 17:52:53 2 Tiny change: 'al state $"(2, 3)"$. Now we ' -> 'al state $(2, 3)$. Now we '
en21 Английский DanAlex 2016-02-06 06:16:36 13 Tiny change: 'e topics. \n\n![ ](h' -> 'e topics. (DP)\n\n![ ](h'
en20 Английский DanAlex 2016-02-06 06:08:27 73
en19 Английский DanAlex 2016-02-06 06:07:17 0 (published)
en18 Английский DanAlex 2016-02-06 06:06:29 167
en17 Английский DanAlex 2016-02-06 06:04:10 103
en16 Английский DanAlex 2016-02-06 06:01:37 327
en15 Английский DanAlex 2016-02-06 06:00:08 2816
en14 Английский DanAlex 2016-02-06 05:21:06 3 Tiny change: ' intended to a general' -> ' intended for a general'
en13 Английский DanAlex 2016-02-06 05:20:52 124
en12 Английский DanAlex 2016-02-06 05:19:38 6
en11 Английский DanAlex 2016-02-06 05:18:56 1292
en10 Английский DanAlex 2016-02-06 05:02:02 1469
en9 Английский DanAlex 2016-02-06 04:48:58 1686
en8 Английский DanAlex 2016-02-06 04:41:41 184
en7 Английский DanAlex 2016-02-06 04:41:03 4 Tiny change: 'we have $B_(2,3)$ and $G_(1,1)$.\n\n##' -> 'we have $B(2, 3)$ and $G(1, 1)$.\n\n##'
en6 Английский DanAlex 2016-02-06 04:40:46 4 Tiny change: 'e have $B_2,3$ and $G_1,1$.\n\n### ' -> 'e have $B_(2,3)$ and $G_(1,1)$.\n\n### '
en5 Английский DanAlex 2016-02-06 04:40:27 176
en4 Английский DanAlex 2016-02-06 04:38:05 214
en3 Английский DanAlex 2016-02-06 04:36:46 1124
en2 Английский DanAlex 2016-02-06 04:17:07 108
en1 Английский DanAlex 2016-02-06 04:14:52 773 Initial revision (saved to drafts)