Dynamic programming
From NoskeWiki
About
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.
Steps
Solving dynamic programming problems typically involves three steps:
- Characterize the structure and/or a recursive definition for an optimal solution
- Initialize the structure
- Compute the value of an optimal solution in a bottom-up fashion
- Construct an optimal solution from the computed information.
Links
- Dynamic Programming - Wikipedia
- Dynamic Programming Tutorial for Needleman/Wunsch "global alignment" - goes through an example of the Needleman/Wunsch technique
- A Tutorial on Dynamic Programming - a nice list of problems by Michael Trick including the "knapsack problem" and many others