Transcript Dynamic Programming: part 1

Dynamic Programming (1)
1
Dynamic Programming
• The dynamic programming archetype is used to solve
problems that can be defined by recurrences with
overlapping subproblems.
• Invented by mathematician Richard Bellman in the 1950s
to solve optimization problems; later co-opted by computer
scientists.
• The word “programming” in the name is not computer
programming as we know it - it means “planning”.
2
Dynamic Programming
• The basic idea:
– Set up a recurrence of some sort, relating a solution to a large
problem instance to one or more solutions of smaller problem
instances.
– Solve each of the smaller problem instances once.
– Record these solutions in a lookup table.
– Build the solution to the large instance by looking up the solutions
to the smaller instances in the table.
• Problems that can be solved by dynamic programming are
said to exhibit optimal substructure - you can build an
optimal solution using optimal solutions to smaller
problem instances.
3
Optimal Substructure
• The problem of finding the shortest route to drive between
two cities exhibits optimal substructure:
– Assume the shortest route from Seattle to Los Angeles passes
through Portland and Sacramento.
– That means the shortest route from Seattle to Sacramento must also
pass through Portland. Solving the smaller problem is part of
solving the bigger one.
• On the other hand, finding the cheapest airfare between
two cities does not typically exhibit optimal substructure.
– If the cheapest ticket from Seattle to Prague stops in New York and
Frankfurt, we usually can’t assume that the cheapest ticket from
Seattle to Frankfurt stops in New York.
4
Dynamic Programming Example:
Fibonacci Numbers
• The Fibonacci numbers are defined by the following
recurrence relation:
• 𝐹 𝑛 = 𝐹 𝑛 − 1 + 𝐹 𝑛 − 2 , 𝐹 0 = 0, 𝐹 1 = 1
• Consider this program for computing the nth Fibonacci
number:
5
Dynamic Programming Example:
Fibonacci Numbers
• Xxxx
• This algorithm is rather inefficient - it’s exponential in n
(section 2.5 of the book contains the full analysis).
• It’s duplicating a lot of work, since Fibonacci(n – 3) is
computed twice (once for the n – 1 call and once for the n
– 2 call), and results further back are duplicated even more.
6
Dynamic Programming Example:
Fibonacci Numbers
• This algorithm performs a linear, not exponential, number
of additions. Much nicer.
• We’re storing only 2 prior results, not all of them - but we
7
did need to calculate all of them.
Dynamic Programming
• The reason that Fibonacci numbers are a trivial example is
that the optimal substructure is inherent in the definition of
the problem.
• The difficult part of devising most dynamic programming
algorithms is finding the optimal substructure in the first
place - most problems don’t have obvious, well-structured
recurrence relations.
8
The Coin-Row Problem
• There is a row of n coins whose values are positive
integers c1, c2, ..., cn - not necessarily distinct or in any
particular order.
• The goal is to pick up the maximum possible amount of
money without picking up any two adjacent coins.
• Example: What is the best solution for the list of coins {10,
3, 5, 9, 1, 1, 6}?
• After looking at it for a while, we can see that the best we
can do is 25 - taking the 10, the 9, and the 6 and skipping
the 3, the 5, and the 1, 1. But what’s an algorithm for this?
9
The Coin-Row Problem
• We can devise a recurrence relation for this:
𝐹 𝑛 = max 𝑐𝑛 + 𝐹 𝑛 − 2 , 𝐹 𝑛 − 1 ,
𝐹 0 = 0, 𝐹 1 = 𝑐1
• We can also devise a program to calculate F(n) given our
array of cn, where F(n) denotes the maximum amount from
first n coins
• Complexity? Θ(n) in both time and space
10
Making Change
• Given a list of coin denominations d1 < d2 < ... < dm, where
d1 = 1, find the minimum possible number of coins
necessary to create change for amount n.
• If we did not have d1 = 1, solutions wouldn’t always be
possible.
• Define F(n) as the minimum number of coins necessary to
create change for amount n
𝐹 𝑛 = min 𝐹 𝑛 − 𝑑𝑗 + 1, ∀𝑛 > 0
𝑗:𝑛≥𝑑𝑗
• This is very much like the previous problem, only now we
have to minimize over at most m different possibilities
11
Making Change
• Complexity: Θ(n) space, Θ(mn) time
12
Multi-Dimension
• So far, the problems we’ve looked at have had
onedimensional structure - to find the solution for n we
look back to the solutions for previous values of n.
• We can also solve problems with 2 (or 3, or k) dimensions.
13
Robot Coin Collection
• Consider an n * m grid, where some cells have coins in
them and others do not.
• A robot starts at the upper-left corner, can move only one
cell right or one cell down at every step, and picks up
every coin it encounters.
• The goal: collect the most coins possible by the time the
robot gets to the lower-right corner of the board.
14
Robot Coin Collection
• Here’s an example board: what’s the best path through it?
• The best path gets 5 coins; there are choices for where to
turn, but on this board we must take those 5 coins
15
Robot Coin Collection
• What’s the recurrence relation for calculating each cell of the
matrix, given that cij for 1 ≤ i ≤ n, 1 ≤ j ≤ m is equal to 1 if there is a
coin at cell (i, j) and 0 if not?
𝐹 𝑖, 𝑗 = max 𝐹 𝑖 − 1, 𝑗 , 𝐹 𝑖, 𝑗 − 1 + 𝑐𝑖𝑗 , 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚
𝐹 0, 𝑗 = 0, 1 ≤ 𝑗 ≤ 𝑚
𝐹 𝑖, 0 = 0, 1 ≤ 𝑖 ≤ 𝑛
• F(i, j) denotes the most coins by the time the robot gets to the cell
(i, j)
16
Robot Coin Collection
𝐹 𝑖, 𝑗 = max 𝐹 𝑖 − 1, 𝑗 , 𝐹 𝑖, 𝑗 − 1 + 𝑐𝑖𝑗 , 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚
𝐹 0, 𝑗 = 0, 1 ≤ 𝑗 ≤ 𝑚
𝐹 𝑖, 0 = 0, 1 ≤ 𝑖 ≤ 𝑛
17
Robot Coin Collection
Complexity? Θ(nm) time, Θ(nm) space
18
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We can proceed in 2 dimensions...
0
Each cell represent the
maximum # of coins the robot
can collect after it arrives in
the particular cell.
19
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We could also do this one row or column at a time, rather
than simultaneously in two dimensions...
0
0
0
0
1
1
20
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We could also do this one row or column at a time, rather
than simultaneously in two dimensions...
0
0
0
0
1
1
0
1
1
2
2
2
21
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We could also do this one row or column at a time, rather
than simultaneously in two dimensions...
0
0
0
0
1
1
0
1
1
2
2
2
0
1
1
3
3
3
22
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We could also do this one row or column at a time, rather
than simultaneously in two dimensions...
0
0
0
0
1
1
0
1
1
2
2
2
0
0
1
2
1
2
3
3
3
3
3
4
23
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We could also do this one row or column at a time, rather
than simultaneously in two dimensions...
0
0
0
0
1
1
0
1
1
2
2
2
0
0
1
2
1
2
3
3
3
3
3
4
1
2
2
3
3
5
24
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We could also do this one row or column at a time, rather
than simultaneously in two dimensions...
0
0
0
0
1
1
0
1
1
2
2
2
0
0
1
2
1
2
3
3
3
3
3
4
1
2
2
3
3
5
1
2
3
3
4
5
25
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We can proceed in 2 dimensions...
0
0
0
0
1
1
0
0
0
1
1
26
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We can proceed in 2 dimensions...
0
0
0
0
1
1
0
1
1
2
2
2
0
0
1
2
1
2
1
2
27
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We can proceed in 2 dimensions...
0
0
0
0
1
1
0
1
1
2
2
2
0
0
1
2
1
2
3
3
3
1
2
2
1
2
3
28
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We can proceed in 2 dimensions...
0
0
0
0
1
1
0
1
1
2
2
2
0
0
1
2
1
2
3
3
3
3
3
4
1
2
2
3
1
2
3
3
29
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We can proceed in 2 dimensions...
0
0
0
0
1
1
0
1
1
2
2
2
0
0
1
2
1
2
3
3
3
3
3
4
1
2
2
3
3
5
1
2
3
3
4
30
Robot Coin Collection
• How can we calculate the maximum number of coins?
• We can proceed in 2 dimensions...
0
0
0
0
1
1
0
1
1
2
2
2
0
0
1
2
1
2
3
3
3
3
3
4
1
2
2
3
3
5
1
2
3
3
4
5
31
Path Counting
1
• Consider the problem of counting the number of shortest
paths from point A to point B in a city with perfectly
horizontal streets and vertical avenues
A
(0,0)
(m,0)
(m,n-1)
(0,n)
B
(m-1,n) (m,n)
F(m,n) = F(m-1,n)+ F(m,n-1) for
n > 1,
F(0,0) = 0, F(0,i)= F(j,0)=1
0<j<=m, 0<i<=n
32