DP

Revision en1, by DanAlex, 2016-02-06 04:14:52

Someone of you demanded 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

Tags dp, dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en29 English DanAlex 2017-08-10 00:20:16 1 Tiny change: '_\n\n[cut]\n\n### Cu' -> '_\n\n[cut].\n\n### Cu'
en28 English DanAlex 2017-08-08 03:26:57 9 Tiny change: 'blic._\n\n### Cu' -> 'blic._\n\n[cut]\n\n### Cu'
en27 English DanAlex 2016-03-21 03:46:03 9 Tiny change: ' by step. [cut]\n\n\n### Ligh' -> ' by step. \n### Ligh'
en26 English DanAlex 2016-03-21 03:45:25 2 Tiny change: ' [cut]\n\n### Li' -> ' [cut]\n\n\n### Li'
en25 English DanAlex 2016-02-07 15:37:06 6 Tiny change: 'p by step.\n\n### Li' -> 'p by step. [cut]\n\n### Li'
en24 English DanAlex 2016-02-07 15:35:10 0 Added tags.
en23 English DanAlex 2016-02-06 17:53:59 2 Tiny change: '\n#### Stare expansio' -> '\n#### State expansio'
en22 English DanAlex 2016-02-06 17:52:53 2 Tiny change: 'al state $"(2, 3)"$. Now we ' -> 'al state $(2, 3)$. Now we '
en21 English DanAlex 2016-02-06 06:16:36 13 Tiny change: 'e topics. \n\n![ ](h' -> 'e topics. (DP)\n\n![ ](h'
en20 English DanAlex 2016-02-06 06:08:27 73
en19 English DanAlex 2016-02-06 06:07:17 0 (published)
en18 English DanAlex 2016-02-06 06:06:29 167
en17 English DanAlex 2016-02-06 06:04:10 103
en16 English DanAlex 2016-02-06 06:01:37 327
en15 English DanAlex 2016-02-06 06:00:08 2816
en14 English DanAlex 2016-02-06 05:21:06 3 Tiny change: ' intended to a general' -> ' intended for a general'
en13 English DanAlex 2016-02-06 05:20:52 124
en12 English DanAlex 2016-02-06 05:19:38 6
en11 English DanAlex 2016-02-06 05:18:56 1292
en10 English DanAlex 2016-02-06 05:02:02 1469
en9 English DanAlex 2016-02-06 04:48:58 1686
en8 English DanAlex 2016-02-06 04:41:41 184
en7 English 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 English 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 English DanAlex 2016-02-06 04:40:27 176
en4 English DanAlex 2016-02-06 04:38:05 214
en3 English DanAlex 2016-02-06 04:36:46 1124
en2 English DanAlex 2016-02-06 04:17:07 108
en1 English DanAlex 2016-02-06 04:14:52 773 Initial revision (saved to drafts)