DP

Revision en2, by DanAlex, 2016-02-06 04:17:07

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.

  1. Establish the environment (The Shire)
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)