Lesson 7.1: Memoization
Memoization is a top-down approach to solving dynamic programming problems. It stores the results of expensive function calls and reuses them when the same inputs occur again.
📌 Key Points
- Memoization avoids repeated computation by caching results.
- Implemented using recursion + hash maps or arrays.
- Reduces exponential time to polynomial in many problems.
- Useful in problems like Fibonacci, climbing stairs, etc.
- Top-down approach: solve and memoize subproblems.
- Each subproblem is solved only once.
- Best when problem has overlapping subproblems and optimal substructure.
🧪 Examples
# 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]
# Climbing Stairs
memo = {}
def climb(n):
if n <= 2: return n
if n in memo: return memo[n]
memo[n] = climb(n-1) + climb(n-2)
return memo[n]
Lesson 7.2: Tabulation
Tabulation is the bottom-up method of solving dynamic programming problems. It solves all related subproblems first and builds up the final answer.
📌 Key Points
- Tabulation uses iteration instead of recursion.
- Space-efficient and faster than memoization in practice.
- Fills up a DP table from base cases to the final result.
- Best for problems with small input sizes or strict memory needs.
- Bottom-up approach: solve smallest subproblems first.
- Common in coin change, knapsack, and LIS problems.
- Easy to convert from recursive to iterative with a table.
🧪 Examples
# Fibonacci with tabulation
def fib(n):
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# Climbing Stairs
def climb(n):
dp = [0] * (n+1)
dp[1], dp[2] = 1, 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
Lesson 7.3: Classic DP Problems
Dynamic programming shines in solving classic optimization and counting problems. These include subsequence problems, grid paths, knapsack, and more.
📌 Key Points
- Fibonacci and Climbing Stairs: basic recursion to DP shift.
- 0/1 Knapsack: pick-or-not-pick paradigm.
- Longest Common Subsequence: string alignment, diff tools.
- Coin Change: minimum number of coins to make target.
- Grid Unique Paths: movement restricted to down/right.
- Subset Sum: can we form a sum from given numbers?
- Palindrome Partitioning: DP + string problem fusion.
🧪 Examples
# Longest Common Subsequence
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
# 0/1 Knapsack Problem
def knapsack(W, wt, val, n):
dp = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i == 0 or w == 0:
dp[i][w] = 0
elif wt[i-1] <= w:
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]