Dynamic Programming
2/6/25
Announcements
● Homework 4 due March 18th
● Quiz 3 + Quiz 2 retake today
○ I was surprised more people didn’t retake Quiz 1 last time
● Spring Break!
Harder Example Write a recursive algorithm to find
the minimum number of coins to
make change.
To be more specific…
GIVEN:
D: A list of denominations of coins (e.g. 5, 10, 12, 15)
l: the length of the denominations list (number of possible coins)
a: An amount of money you want to make change for (integer value)
RETURN:
m: The minimum number of coins to make change for a
We tried this with a greedy algorithm (choose largest coin)
It worked for some denominations:
E.g. 1, 5, 10, 25, 50
It did not work for others.
E.g. 1, 3, 6, 12, 24, 30
Simpler example: 1, 4, 6
Let’s try recursion for a different approach.
1. What’s the simplest possible case?
Denominations: 1, 4, 6
1. What’s the simplest possible case?
Denominations: 1, 4, 6
Making change for 0 cents: return 0 coins
2. Play around and visualize!
Denominations: 1 4 6
0:
1: 1 7: 6 1 13: 6 6 1
2: 1 1 8: 4 4 14: 6 4 4
3: 1 1 1 9: 4 4 1 15: 6 4 4 1
4: 4 10: 6 4 16: 6 6 4
5: 4 1 11: 6 4 1 17: 6 6 4 1
6: 6 12: 6 6 18: 6 6 6
2. Play around and visualize! (consider non-optimal
solutions too!)
Denominations: 1 4 6
0:
1: 1 7: 6 1 13: 6 6 1 , 4 4 1 1
2: 1 1 8: 4 4 14: 6 4 4 , 6 6 1 1 , 4 4 1 1 1
3: 1 1 1 9: 4 4 1 15: 6 4 4 1 , 6 6 1 1 1
4: 4 10: 4 16: 6 6 4 , 6 4 4 1 1
6
5: 4 1 11: 6 4 1 17: 6 6 4 1 , 6 4 4 1 1 1
6: 6 12: 6 6 18: 6 6 6 , 6 6 4 1 1 , 6 4 4 4
Note: these examples are not exhaustive
3. Relate hard cases to simpler cases
Denominations: 1 4 6
0:
1: 1 7: 6 1 13: 6 6 1
2: 1 1 8: 4 4 14: 6 4 4
3: 1 1 1 9: 4 4 1 15: 6 4 4 1
4: 4 10: 6 4 16: 6 6 4
5: 4 1 11: 6 4 1 17: 6 6 4 1
6: 6 12: 6 6 18: 6 6 6
3. Relate hard cases to simpler cases
Denominations: 1 4 6
0:
1: 1 7: 6 1 13: 6 6 1
2: 1 1 8: 4 4 14: 6 4 4
3: 1 1 1 9: 4 4 1 15: 6 4 4 1
4: 4 10: 6 4 16: 6 6 4
5: 4 1 11: 6 4 1 17: 6 6 4 1
6: 6 12: 6 6 18: 6 6 6
3. Relate hard cases to simpler cases
Denominations: 1 4 6
0:
1: 1 7: 6 1 13: 6 6 1
2: 1 1 8: 4 4 14: 6 4 4
3: 1 1 1 9: 4 4 1 15: 6 4 4 1
4: 4 10: 6 4 16: 6 6 4
5: 4 1 11: 6 4 1 17: 6 6 4 1
6: 6 12: 6 6 18: 6 6 6
4. Generalize the pattern
4. Generalize the pattern
If our denominations are D0 through Dn, we can make change for amount X by
adding coin Di to a solution for amount X - Di
Recall that we are minimizing the number of coins used.
So: change(X) = 1 + min([change[X - Di] for i = 0 to n])
More formally
Denominations: 1, 4, 6
F(n) = 1 + min(F(n-1), F(n-4), F(n-6))
5. Write code
Dynamic programming
What is the time complexity of this algorithm?
Denominations: 1, 3, 6, 12, 24, 30
def change(amt, num_coins, denom_list):
if amt == 0:
return 0
# subtract the largest possible value out of the amount
# calculate previous amount
result = [Link]
for i in range(num_coins):
if denom_list[i] <= amt:
new_amt = amt - denom_list[i]
result_for_this_coin = change(new_amt, num_coins, denom_list)
if result_for_this_coin + 1 < result:
result = result_for_this_coin + 1
return result
6^n
[Link]
6^n Really bad
[Link]
[Link]
How can
we
improve?
Memoization
● Keep a hash table mapping inputs to results
● What is the time complexity?
Memoization
● Keep a hash table mapping inputs to results
● O(n*m)-ish time complexity → huge improvement!
● Still a fair amount of overhead
○ Recursive calls
○ Cache performance
○ Hash collisions
Can we
do even
better?
Dynamic programming
● Yes, the name is super uninformative
● Basic idea: store answers in a table
● Populate table in an order that ensures you always have the necessary
answers to smaller problems
● Works on the same principles as recursion, but without recursion
Conceptual steps in dynamic programming
1. Formulate your problem recursively
2. Show that the number of different instances of your recurrence is bounded by
a polynomial.
3. Specify an order of evaluation for the recurrence so you always have what you
need.
Implementation steps
1. Base case → initialization of array
2. Body of function → body of loop (arguments → loop variables)
3. Recursive calls → array lookups
4. Returns → store in array
Equivalence between recursion and dynamic programming
1. Base case → initialization of array
2. Body of function → body of loop
○ (arguments → loop variables)
3. Recursive calls → array lookups
4. Returns → store in array
def fib(n): def fib(n):
if n <= 1 : table = [] * (n + 1)
return n table[0] = 0
return fib(n - 1) + fib(n - 2) table[1] = 1
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
Demo
Table representation of dynamic programming
N 0 1 2 3 4 5 6 7 8 9
Answer
Denominations: 1, 2, 4
Practice problem: fill out the table for these denominations
N 0 1 2 3 4 5 6 7 8 9
Answer
Denominations: 1, 3, 5
When can we use dynamic programming?
Optimal substructure: The details of our past solutions won’t affect our current
solution.
Image source: Tarun Kumar
When can we use dynamic programming?
The principle of optimality: “An optimal policy has the property that whatever the initial
state and initial decision are, the remaining decisions must constitute an optimal policy
with regard to the state resulting from the first decision.“
When can we use dynamic programming?
Image source: interviewbit
When can we use dynamic programming?
Intuitively, these circumstances often occur when we are
dealing with ordered sequences
Intuition building
Can we use dynamic programming to calculate N!?
Intuition building
Can we use dynamic programming for the coin change problem?
Intuition building
Can we use dynamic programming for the following problem: given a set of points
on an Cartesian plane, find the shortest path that visits all points?
In-class problem
Convert our recursive coin change implementation from last class into dynamic
programming
def change(amt, num_coins, denom_list):
if amt == 0:
return 0
# subtract the largest possible value out of the amount
# calculate previous amount
result = [Link]
for i in range(num_coins):
if denom_list[i] <= amt:
new_amt = amt - denom_list[i]
result_for_this_coin = change(new_amt, num_coins, denom_list)
if result_for_this_coin + 1 < result:
result = result_for_this_coin + 1
return result
Intuition building
Recall the problem where Little Red Riding Hood is choosing fruits to bring to her
grandmother.
● Her basket has a limited capacity. Within this capacity, she wants to choose the
fruits her grandmother will like the most.
● If she can cut the fruit into arbitrarily small units, a greedy algorithm will work.
● If she cannot, a greedy algorithm will not work.
Will dynamic programming work on variant where fruits cannot be cut?
The knapsack problem
The classic Knapsack problem is typically put forth as:
A thief breaks into a store and wants to fill their knapsack with as much value in goods as
possible before making their escape. Given the following list of items available, what should
they take?
First step: formulate the problem recursively
What are the subproblems? How can we make this problem
simpler?
First step: formulate the problem recursively
What are the subproblems? How can we make this problem
simpler?
F(i, w) = max([F(i - 1, w), Vi + F(i - 1, w - wi), F(i, w - 1)])
Discussion Problem
Draw the dynamic programming table for the following instance of the knapsack
problem:
WA = 4 VA = 2
WB = 1 VB = 1 A B C
1
WC = 2 VC = 3
2
Weight limit: 5 4
5
Discussion problem
You are a given a sentence. You need to choose words from it such that you get the
most possible letters but no two adjacent words are selected.
How can you solve this problem with dynamic programming?