Dynamic Programming¶
Solve complex optimization problems by remembering smaller results. This notebook covers core ideas, worked examples (coin change & knapsack), lightweight runnable cells, and exercises to practice reconstruction and memoization.
Learning goals
Explain optimal substructure and overlapping subproblems.
Implement tabulation and memoization patterns.
Reconstruct solutions (not just counts) for coin-change and knapsack.
# 0/1 Knapsack — worked example (small)
```python
# Items: (value, weight)
items = [(6,2),(10,3),(12,4)]
max_w = 7
n = len(items)
# DP table: dp[i][w] = max value using first i items and capacity w
dp = [[0]*(max_w+1) for _ in range(n+1)]
keep = [[False]*(max_w+1) for _ in range(n+1)]
for i in range(1,n+1):
val, wt = items[i-1]
for w in range(max_w+1):
if wt <= w and dp[i-1][w-wt] + val > dp[i-1][w]:
dp[i][w] = dp[i-1][w-wt] + val
keep[i][w] = True
else:
dp[i][w] = dp[i-1][w]
# reconstruct
w = max_w
picked = []
for i in range(n,0,-1):
if keep[i][w]:
picked.append(items[i-1])
w -= items[i-1][1]
print('Max value:', dp[n][max_w])
print('Picked items:', picked)
```
Exercises¶
Implement
dp_min_coins(coins, amount)that returns the optimal coin multiset (not just count).Modify the Fibonacci example to use memoization (recursion + cache) and measure time vs iterative DP for n=30.
Implement the 0/1 knapsack DP and reconstruct selected items for a small test case.
Hints and solution reveals are in the `solutions` folder. Start with small amounts and item sizes.Summary / Key Takeaway¶
Dynamic programming identifies overlapping subproblems and reuses solutions via memoization or tabulation.
Use DP when optimal substructure and overlapping subproblems are present; prefer greedy when a local choice is provably safe.
Next: we’ll move to data loading and wrangling, where DP-style caching patterns appear in memoized feature computations.
def fibonacci(n):
if n <= 1:
return n
dp = [0, 1]
for index in range(2, n + 1):
dp.append(dp[index - 1] + dp[index - 2])
return dp[n]
print(fibonacci(8))21
Core Explanation¶
Dynamic programming is useful when:
a problem can be broken into smaller overlapping subproblems
solving the same subproblem repeatedly would waste time
storing previous results helps improve efficiency
Worked Example¶
The Fibonacci sequence is a common teaching example because the naive recursive approach repeats the same subproblems many times.
Why dynamic programming helps here
Instead of recomputing earlier Fibonacci values repeatedly, we build them once and reuse them.
Business and ML Connection¶
Dynamic programming ideas appear in optimization, scheduling, planning, sequence analysis, and decision-making problems.
Examples include:
budgeting under constraints
resource allocation
route optimization variants
sequence alignment and structured prediction
Quick Quiz¶
Why is dynamic programming often faster than naive repeated computation?¶
values = [3, 7, 2, 9]
best = [0]
for value in values:
best.append(best[-1] + value)
print(best[-1])21
Exercises¶
Explain dynamic programming in your own words.
Identify one problem where overlapping subproblems may appear.
Compare greedy thinking and dynamic programming conceptually.
Quick Summary
dynamic programming solves overlapping subproblems efficiently
it stores intermediate answers for reuse
it is especially useful in optimization and planning problems
Final Note¶
Dynamic programming is a powerful reminder that good algorithm design often comes from noticing structure in a problem, not just from writing more code.
8. Interactive Code¶
Expected output
[0, 1, 1, 2, 3, 5, 8]Expected output
7
4