Dynamic Programming (DP)
Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure.
1. Core Concepts
- Overlapping Subproblems: The problem can be broken down into subproblems which are reused several times. (e.g., in Fibonacci,
fib(5)needsfib(4)andfib(3), andfib(4)needsfib(3)andfib(2)). - Optimal Substructure: The optimal solution of the main problem can be constructed from the optimal solutions of its subproblems.
2. Approaches
There are two main ways to implement DP:
Top-Down (Memoization)
Start from the main problem and break it down. If you solve a subproblem, store the result ("memoize" it) so you don't have to solve it again. This is essentially Recursion + Caching.
# Fibonacci with Memoization
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n-1) + fib(n-2)
return memo[n]Bottom-Up (Tabulation)
Start with the smallest subproblems and build up to the main problem. This is usually done with Iteration (loops) and filling up a table (array).
# Fibonacci with Tabulation
def fib(n):
if n <= 1:
return n
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i-1] + table[i-2]
return table[n]3. Common Problems
- Fibonacci Sequence
- Knapsack Problem
- Longest Common Subsequence
- Shortest Path (e.g., Bellman-Ford, Floyd-Warshall)