Foundations‎ > ‎Algorithms‎ > ‎

Dynamic Programming

Dynamic Programming is mostly used for solving optimization problems (these are problems that have one or more optimal solutions). Normally, if an optimal solution to a problem contains overlapping subproblems and each subproblem has an optimal solution within it (optimal substructure), then this problem is the perfect candidate for dynamic-programming. (e.g. fastest way through factory to stations Si,j is through Si,j-1. This implies that Si,j-1 is the fastest way through the factory up to that point).

Steps of development of a a dynamic-programming algorithm:
  1. Characterize the strucure of an optimal solution.
  2. Recursively define the value of an optimal solution.
  3. Compute the value of an optimal solution in a bottom-up fashion (this normally requires saving the values into one or more tables as you go - you may need to use this for step 4).
  4. Construct an optimal solution from computed information.