Dynamic Programming
CENG 303
Design and Analysis
of Algorithms
Introduction
• Allows us to solve our problems in polynomial time
• Careful brute-force
• Try all possible solution in a smart way
• Create subproblems
• Re-use solutions
• Fibonacci numbers
• Shortest path problems
• Text justification
• Blackjack
Fibonacci Numbers
𝐹1 = 𝐹2 = 1
• ቊ
𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2
• Compute 𝑛th Fibonacci number
Fibonacci Numbers
• Naïve recursive algorithm
• fib(n) = if n≤2: f = 1
else f = fib(n-1) + fib(n-2)
return f
• 𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑇(𝑛 − 2) + 𝑂(1)
• Exponential
Fibonacci Numbers
• 𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑇(𝑛 − 2) + Θ(1)
• 𝑇 𝑛 = 𝑇 𝑛−2 + 𝑇 𝑛−3 + Θ 1 +
𝑇(𝑛 − 3) + 𝑇(𝑛 − 4) + Θ(1) + Θ(1)
• 𝑇 𝑛 = 𝑇 𝑛−3 + 𝑇 𝑛−4 + Θ 1 +
𝑇 𝑛−4 + 𝑇 𝑛−5 + Θ 1 +
𝑇 𝑛−4 + 𝑇 𝑛−5 + Θ 1 +
𝑇 𝑛−5 + 𝑇 𝑛−6 + Θ 1 +
Θ(1) + Θ(1) + Θ(1)
Fibonacci Numbers
𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑇(𝑛 − 2) + Θ(1)
𝑇(𝑛) ≥ 𝑇(𝑛 − 2) + 𝑇(𝑛 − 2) + Θ(1)
≥ 2𝑇(𝑛 − 2) + Θ(1)
≥ Θ(2𝑛/2 )
Memoized DP Algorithm
memo = {}
fib(n)
if n in memo: return memo[n]
if n ≤2 : f=1
else f=fib(n-1) + fib(n-2)
memo[n] = f
return f
Memoized DP Algorithm
𝐹𝑛
𝐹𝑛−1
𝐹𝑛−2
𝐹𝑛−2 𝐹𝑛−3 𝐹𝑛−3 𝐹𝑛−4
Memoized DP Algorithm
𝐹𝑛
𝐹𝑛−1
𝐹𝑛−2
𝐹𝑛−2 𝐹𝑛−3 𝐹𝑛−3 𝐹𝑛−4
Memoized DP Algorithm
𝐹𝑛
𝐹𝑛−1
𝐹𝑛−2
𝐹𝑛−2 𝐹𝑛−3 𝐹𝑛−3 𝐹𝑛−4
Memoized DP Algorithm
𝐹𝑛
𝐹𝑛−1
𝐹𝑛−2
𝐹𝑛−2 𝐹𝑛−3 𝐹𝑛−3 𝐹𝑛−4
Memoized DP Algorithm
fib(k) only recurses the first time it’s called
to calculate fib(k) the recursion happens only 𝑛 times
fib(1), fib(2), fib(3),…, fib(n)
Each recursion cost Θ(1)
Memoized calls cost Θ(1)
Θ(𝑛)
Dynamic Programming
• memorize (remember)
• re-use solutions to subproblems
• total time = the number of subproblems X time for per subproblem
• We do not need to count memoized recursions
Bottom-up DP Algorithm
fib = {}
for k in range(1,n+1)
if k≤2 : f=1
else f=fib[k-1] + fib[k-2]
fib[k] = f
return fib[n]
Bottom-up DP Algorithm
• Exactly same computation as the memoized version
• Topological sort of subproblem dependency DAG
𝐹𝑛−3 𝐹𝑛−2 𝐹𝑛−1 𝐹𝑛
• Can save space, we need only the last two values
Dynamic Programming (DP)
Five “easy” steps
Easy means interdependent
[Link] subproblems
[Link] (part of solution)
[Link] subproblem solutions
[Link] & memoize
[Link] original problem
Fibonacci Numbers
[Link] subproblems
fib(k) for 𝑘 = 1, … , 𝑛 | number of subproblems is 𝑛
[Link] (part of solution)
nothing | number of choices is 1
[Link] subproblem solutions
recurrence | fib(k) = fib(k-1) + fib(k-2) | Θ(1)
[Link] & memorize
topological order | for 𝑘 = 1, … , 𝑛 | check subprob recurrence is acyclic
[Link] original problem : fib(n)
Shortest Paths
• Guessing
s v
Shortest Paths
• Guessing
• What is the last edge? Maybe (𝑢, 𝑣)?
• To find best guess, try all edges going 𝑣 and use best
s u v
Shortest Paths
• Guessing
• What is the last edge? Maybe (𝑢, 𝑣)?
• To find best guess, try all edges going 𝑣 and use best
• Key: small (polynomial) number of possible guesses per subproblem
• typically this dominates time/subproblem
s u v
Shortest Paths
𝛿 𝑠, 𝑣 ∀𝑣
• recursive formulation
𝛿 𝑠, 𝑣 = min 𝛿 𝑠, 𝑢 + 𝑤 𝑢, 𝑣 𝑢, 𝑣 𝜖𝐸}
the base case: 𝛿 𝑠, 𝑠 = 0
s u v
Shortest Paths
The drawback:
Takes infinite time if the graph is cyclic
𝛿 𝑠, 𝑣
a
𝛿 𝑠, 𝑎
s v
𝛿 𝑠, 𝑏
b
𝛿 𝑠, 𝑠 𝛿 𝑠, 𝑣
Shortest Paths
• Infinite time with cycles
• DAGs-> 𝑂(𝑉 + 𝐸)
• the number of subproblem is 𝑉
• time for per subproblem is indegree(𝑉) + 1
• total time = σ𝑣∈𝑉 indegree 𝑉 + 1 = 𝜃(V + E)
• subproblem dependencies should be acyclic
Shortest Paths
• How to solve?
• Convert cyclic graph to acyclic graph
time
Shortest Paths
• 𝛿𝐾 𝑠, 𝑣 = min 𝛿𝐾−1 𝑠, 𝑢 + 𝑤 𝑢, 𝑣 𝑢, 𝑣 𝜖𝐸}
• The number of subproblems:𝑉 2
time
Shortest Paths
• Infinite time with cycles
• DAGs-> 𝑂(𝑉 + 𝐸)
• the number of subproblem is 𝑉
• time for per subproblem is indegree(V)+1
• total time = σ𝑣∈𝑉 indegree 𝑉 + 1 = 𝜃(𝐸 + 𝑉)
• subproblem dependencies should be acyclic
Text Justification
• split given text into “good” lines
• text is a list of words
(page width−total width) 𝑘
• badness(i,j) = ቊ
∞ if do not fit
• use words[i:j] as line
Text Justification
1. Subproblems: suffixes words[𝑖: ]
• number of subproblems: |𝑛
2. guess: where to start the 2nd line
• number of choices: |≤𝑛−𝑖 =𝑂 𝑛
3. recurrence: 𝑇𝐽(𝑖)
i
𝑇𝐽 𝑗 +badness(𝑖,𝑗)
min for 𝑗 in range (𝑖+1,𝑛+1) j
Text Justification
4. topological order
• 𝑇𝐽(𝑛) = 0
• 𝑖 = 𝑛, 𝑛 − 1, 𝑛 − 2, … , 0
• total time = Θ(𝑛2 )
5. Original problem: DP(0)
BlackJack
• The goal of blackjack is to beat the dealer's hand without going over 21.
• Face cards are worth 10. Aces are worth 1 or 11, whichever makes a better
hand.
• Each player starts with two cards, one of the dealer's cards is hidden until the
end.
• To 'Hit' is to ask for another card. To 'Stand' is to hold your total and end your
turn.
• If you go over 21 you bust, and the dealer wins regardless of the dealer's
hand.
• If you are dealt 21 from the start (Ace & 10), you got a blackjack.
BlackJack
• Blackjack usually means you win 1.5 the amount of your bet. Depends on the casino.
• Dealer will hit until his/her cards total 17 or higher.
• Doubling is like a hit, only the bet is doubled, and you only get one more card.
• Split can be done when you have two of the same card - the pair is split into two
hands.
• Splitting also doubles the bet, because each new hand is worth the original bet.
• You can only double/split on the first move, or first move of a hand created by a split.
• You cannot play on two aces after they are split.
• You can double on a hand resulting from a split, tripling or quadrupling you bet.
BlackJack
• Perfect-Information Blackjack
• deck = 𝑐0 , 𝑐1 , … , 𝑐𝑛−1
• the sequence of cards in the deck is known
• 1 player vs dealer
• $1 bet per game
• there is no split, no doubling
• maximize the earning
BlackJack
1. subproblems: suffix 𝑐𝑖
• number of subproblems: |𝑛
2. guess: how many hits?
• number of choices |≤ 𝑛
3. recurrence
• Blackjack(i) = max (outcome ∈ {−1,0,1} | 𝑂(𝑛)
+ Blackjack(j)
for # hits in range (0,n) | 𝑂(𝑛)
• 𝑗 = 𝑖 + 4 + #hits + #𝑑𝑒𝑎𝑙𝑒𝑟 hits
• time per subproblem O(𝑛2 )
BlackJack
4. topological order:
for i in reversed(range(n))
4. Solution:
Blackjack(o)
BlackJack
outcomes
1
1
0
-1
i i+4 i+5 i+6 i+7
valid plays