Dynamic programming

From NoskeWiki
Jump to: navigation, search
This represents a page the author has not finished yet, but hopefully will finish soon! As a wiki I can't guarantee the accuracy on any of these pages, but pages with this logo I can almost certainly guarantee DO contain errors and/or big omissions.


Dynamic programming is a way of breaking large problems into smaller problems and minimizing the amount of re-calculation needed by the "memorization" of answers to the smaller problems. This page is still under construction, but the links below give some good examples of how dynamic programming works.


Solving dynamic programming problems typically involves three steps:

  1. Characterize the structure and/or a recursive definition for an optimal solution
  2. Initialize the structure
  3. Compute the value of an optimal solution in a bottom-up fashion
  4. Construct an optimal solution from the computed information.