dynamic programming (DP)

Dynamic programming (DP) is a method for solving a problem by breaking it into simpler overlapping subproblems, solving each one only once, and reusing the stored result whenever the same subproblem comes up again. It builds on recursion, but it avoids the repeated work that a naive recursive solution would perform.

A problem is a good fit for dynamic programming when it shows two properties. Optimal substructure means that an optimal solution to the whole problem is built from optimal solutions to its subproblems. Overlapping subproblems means that the same subproblems recur many times during the computation, so caching their results pays off. A naive Fibonacci computation makes this concrete:

Two complementary strategies put the idea into practice:

• Top-down, also called memoization, follows the natural recursive structure and stores each subproblem’s result in a lookup table the first time it’s computed.
• Bottom-up, also called tabulation, works iteratively from the smallest subproblems upward, filling a table until it reaches the full problem.

By trading memory for speed, dynamic programming can lower a problem’s time complexity, turning an exponential-time computation into a polynomial-time one. Computing the nth Fibonacci number through naive recursion takes exponential time, whereas a dynamic programming version runs in linear time. Classic applications include shortest-path algorithms, the knapsack problem, sequence alignment, and edit distance between strings.

The mathematician Richard Bellman coined the term in the 1950s. In that context, the word programming refers to planning and optimization in the mathematical sense rather than to writing code.

Related Resources

Tutorial

Thinking Recursively in Python

Learn how to work with recursion in your Python programs by mastering concepts such as recursive functions and recursive data structures.

intermediate python

For additional information on related topics, take a look at the following resources:

• Recursion in Python: An Introduction (Tutorial)
• Scientific Python: Using SciPy for Optimization (Tutorial)
• Hands-On Linear Programming: Optimization With Python (Tutorial)
• Recursion in Python (Course)
• Thinking Recursively With Python (Course)
• Recursion in Python: An Introduction (Quiz)