Dynamic Programming

Internal

• Algorithms

Overview

Dynamic programming algorithms are optimized recursive algorithms, where we store the solution of smaller subproblems and use them in computing the solution for larger subproblems, avoiding duplicate work and yielding superior running times. The classic example where the difference between the straightforward recursive solution and the corresponding dynamic programming solution is obvious is computing Fibonacci numbers.

A dynamic programming solution usually starts with an analysis of the optimal solution ("how would the optimal solution look like, and what happens if a specific element is part or is not part of the optimal solution"). The goal is to express the optimal solution as a recursive function of smaller subproblem solutions. The reasoning used for the optimal solution (n items) applies to an intermediary smaller subproblem of i size.

Once the recurrence expression is established for i, the algorithm proceeds by "brute force" computation of the smaller solutions starting with i = 1, and the selection of the optimal solution at step i by comparing results computed at previous steps and selecting the maximum. This "brute force" approach is feasible because the number of smaller solutions is asymptotically small, so it makes sense to compute them in an efficient running time.

The solution of the smaller subproblems is stored in a global array as the algorithm progresses. This technique is also called memoization. The semantics of storing the solution in the array is that the i^th entry of the array is the solution of the i^th subproblem. In a recursive call, if the smaller problem has been solved already (the array has a value), then that value is used. This is why it is crucial that we solve the subproblems in the right order, from smallest to largest. If the subproblem is not solved when we need it, the problem must be solved and the result stored. Once stored in the array, the subproblem solutions can be retrieved in O(1) later, to be used in computing the solution of larger problems.

The global array is unidimensional or bidimensional, depending on how many dimension the problem has. For example, the maximum weight independent set problem uses a unidimensional array, while the knapsack problem uses a bidimensional array.

The third step of the algorithm is executed after the final optimal solution is computed, and consists in backtracking the array of smaller solutions and establishing what input elements contributed to the optimal solution.

"Dynamic programming" is a term invented by Richard Bellman. Also see:

Principles of Dynamic Programming in "Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming" by Tim Roughgarden

Canonical Use

• Computing Fibonacci numbers
• Maximum weight independent set problem
• The knapsack problem
• The sequence alignment problem
• Compute optimal binary search trees
• Distributed shortest path problem: Bellman-Ford Shortest-Path Algorithm