Dynamic programming is a powerful technique for solving problems by breaking them down into smaller, overlapping subproblems. Instead of solving the same subproblems repeatedly, we store the results and reuse them—a concept called memoization.
The key insight is recognizing when a problem has optimal substructure: the solution to a larger problem can be built from solutions to smaller versions of the same problem. Many classic problems follow this pattern, including the famous Fibonacci sequence.
Consider calculating Fibonacci numbers naively with recursion. To find F(5), we need F(4) and F(3). But to find F(4), we need F(3) and F(2)—notice we're calculating F(3) twice! As numbers get larger, this repetition explodes exponentially.
Dynamic programming solves this by working bottom-up: start with the base cases and build toward the answer, or top-down with memoization to cache results. The bottom-up approach often uses less memory since we only need to remember recent results.
The magic happens when you recognize the recurrence relation—the mathematical relationship between a problem and its subproblems. Once you see this pattern, many seemingly complex problems become straightforward to solve efficiently.
Dynamic programming transforms problems that might take exponential time into linear or polynomial solutions. It's especially powerful for optimization problems, counting problems, and decision problems where you need to consider multiple possibilities.
1def fibonacci(n):
2 """Calculate nth Fibonacci number using dynamic programming"""
3 if n <= 1:
4 return n
5
6 # Only store the last two values we need
7 prev2, prev1 = 0, 1
8
9 for i in range(2, n + 1):
10 current = prev1 + prev2
11 prev2, prev1 = prev1, current
12
13 return prev1