We're sorry but this app doesn't work properly without JavaScript enabled. Please enable it to continue.

This lesson's interactive features are locked, please to keep using them

Intro to Dynamic Programming

"Those who cannot remember the past are condemned to repeat it."
– George Santayana (but also Dynamic Programming)

Click to play video

Dynamic programming, DP for short, is a powerful optimization technique. Wherever we see a solution to a problem that has repeated iterations for the same inputs, we can optimize it using dynamic programming. The idea is simply to remember the results of subproblems so that we don't have to re-compute them. This can save our algorithms immense amounts of time.

Problems need to have two properties in order to benefit from dynamic programming:

  1. Overlapping subproblems
  2. An "optimal substructure"

Overlapping Subproblems

The core concept behind dynamic programming is to divide a problem into subproblems, and save the result of each subproblem so that it won't need to be computed again. Assuming there are subproblems that repeat, we can save a lot of time by using cached results.

Optimal Substructure

If the optimal solution of the overall problem can be reached by using optimal solutions of its subproblems, then the problem is a good candidate for a dynamic programming algorithm.

For example, the Bellman-Ford algorithm that we covered earlier in this course actually involves dynamic programming! The shortest-path problem has the "optimal substructure" trait.

In the graph above, let's assume we knew only the following 3 facts:

  1. The shortest path from 0 to 3 is 0 -> 2 -> 3
  2. The shortest path from 3 to 6 is 3 -> 5 -> 6
  3. 3 is on the shortest path from 0 to 6

Knowing just those pieces of information, we can guarantee that the shortest path from 0 to 6 is the combination of the two optimal subpaths, i.e. 0 -> 2 -> 3 -> 5 -> 6.