3.txt

The following content is provided
Your support will help MIT OpenCourseWare continue
To make a donation or view additional materials
at ocw.mit.edu.
dynamic programming.
PROFESSOR: Yeah!
Actually, I am really excited because dynamic programming
And it's going to be the next four lectures,
It has lots of different facets.
We don't talk a lot about algorithm design in this class,
And also takes a little while to settle in.
So in general, our motivation is designing new algorithms
is a great way-- or a very general, powerful way
It's especially good, and intended for, optimization
You want to find the best way to do something.
path, the minimum-length path.
an optimization problem, and typically
It's a bit of a broad statement.
as a kind of exhaustive search.
because it leads to exponential time.
you typically get polynomial time.
is approximately careful brute force.
A bit of an oxymoron.
try all possibilities and you do it carefully
There are a lot of problems where essentially
via dynamic programming.
where we don't think there are polynomial time algorithms,
general approach to it.
There's a lot of different ways to think about it.
We're going to warm up today with some fairly easy problems
namely computing Fibonacci numbers.
And computing shortest paths.
we're going to get to more interesting examples
solve the problem in polynomial time.
though, is why is it called dynamic programming?
And I used to have this spiel about, well, you
it's the British notion of the word,
Optimization in American English is something
where you want to set up the program--
where programming comes from originally.
why is it called dynamic programming.
You may have heard of Bellman in the Bellman-Ford algorithm.
And we're going to see Bellman-Ford come up naturally
So here's a quote about him.
invented the name dynamic programming to hide the fact
He was working at this place called Rand,
and hatred for the term research.
because it would be difficult to give
And because it was something not even
Basically, it sounded cool.
So why is the called that?
I mean, now you know.
Just take it for what it is.
All right.
to compute Fibonacci numbers.
I'm going to give you a sneak peak of what
And this equation, so to speak, is
In the end we'll settle on a sort
The basic idea of dynamic programming
solve those subproblems, and reuse the solutions
It's like a lesson in recycling.
So you remember Fibonacci numbers, right?
We've mentioned them before, we're talking about AVL trees,
So this is the usual-- you can think
numbers.
So let's suppose our goal-- an algorithmic problem is,
And I'm going to assume here that that fits in a word.
whatever's constant time per operation.
You all know how to do it.
perspective on things.
but it is-- we're going to apply exactly the same principles
But here it's in a very familiar setting.
And that is, if you want to compute the nth Fibonacci
I'm going to write it this way.
You'll see why I write it this way in a moment.
In the base case it's 1, otherwise
You recursively call Fibonacci of n minus 2.
This is a correct algorithm.
No.
Exponential time.
other than from experience?
T of n represents the time to compute the nth Fibonacci
How can I write the recurrence?
and conquer.
Yeah?
PROFESSOR: Yeah.
I don't know how many you have by now.
we have to compute the n minus first Fibonacci number,
That's these two recursions.
We do constant number of additions, comparisons.
So that's a recurrence.
Well one way is to see this is the Fibonacci recurrence.
There's this plus whatever.
And if you know Fibonacci stuff, that's
Which is bad.
And so another way to solve it-- it's
at least 2 times t of n minus 2.
The bigger n is, the more work you have to do.
to do the n minus first thing.
That will give us a lower bound.
You see that you're multiplying by 2 each time.
How many times can I subtract 2 from n?
And so this is equal to 2 to the n over 2--
is what you get in the base case.
This thing is theta that.
So it's at least that big.
And the base of the exponent.
So that's a bad algorithm.
But I'm going to give you a general approach for making
And that general approach is called memoization.
And this is a technique of dynamic programming.
algorithm.
Yeah.
Whenever we compute a Fibonacci number
And then when we need to compute the nth Fibonacci
Did we already solve this problem?
Otherwise, computer it.
OK.
So you can see how the transformation
You could do this with any recursive algorithm.
which is, we initially make an empty dictionary called memo.
well, check whether this version of the Fibonacci problem,
So if that key is already in the dictionary,
And then once we've computed the nth Fibonacci number,
then we store it in the memo table.
here it is.
So this is a general procedure.
with no side effects I guess, technically.
Now there's a lot of ways to see why it's efficient.
tree.
we compute fn minus 1 and fn minus two
To compute fn minus 1 we compute fn minus 2 and fn minus 3.
And so on.
Because we're only decrementing n by one or two each time.
I should really only have to compute them once.
The first time you call fn minus 3, you do work.
call, this will just get cut off.
Here we might have some recursive calling.
In fact, this already happens with fn minus 2.
has already been done.
So it's clear why it improves things.
because you already did the work in here.
about why this is efficient, which is following.
here.
of thinking about this because recursion
If you're calling Fibonacci of some value, k,
you call Fibonacci of k.
in the memo table you will not recurse.
of calling Fibonacci of k.
does recursion-- does some work.
doing memoized calls of Fibonacci of k,
So the memoized calls cost constant time.
That's when you call Fibonacci of n minus 2,
don't pay anything for it.
to do addition and whatever.
There's no recursion here.
of non-memorized calls, which is the first time you
No theta is even necessary.
At some point we're going to call Fibonacci of 2
All of those things will be called at some point.
But in particular, certainly at most this,
to compute Fibonacci of n.
Indeed it will be exactly n calls that are not memoized.
How much do we have to pay?
is what this recurrence does-- if you ignore
So I will say the non-recursive work per call is constant.
constant-- I'm sorry, is linear.
This is actually not the best algorithm-- as an aside.
uses log n arithmetic operations.
to see that you should take 6046.
We're just going to get to linear today, which
So why linear?
cost constant.
This is an important idea.
down again in a slightly more general framework.
I didn't say why it's called memoization.
you write down all your scratch work.
And to memoize is to write down on your memo pad.
Another crazy term.
And then you remember all the solutions that you've done.
Now these solutions are not really a solution
The problem I care about is computing the nth Fibonacci
To get there I had to compute other Fibonacci numbers.
Because I had a recursive formulation.
But usually when you're solving something
They're not always of the same flavor
some kind of related parts.
is to figure out what are the subproblems.
to know about a dynamic program, is what are the subproblems.
And the idea of memoization is, once you solve a subproblem,
If you ever need to solve that same problem again
So that is the core idea.
is essentially recursion plus memoization.
Fibonacci of 1 through Fibonacci of n.
But to get there we solve these other subproblems.
for any dynamic program, the running time
you might have to solve, or that you do solve,
OK.
And for each of them we spent constant time.
which, in the Fibonacci case I claim is constant,
That's the key.
with dynamic programming.
No recurrences necessary.
Don't count recursions.
The reason is, I only need to count them once.
So I count how many different subproblems do I need to do?
I do work, I do some amount of work,
be double counting.
and then this will solve it.
In general, dynamic programming is a super simple idea.
It's basically just memoization.
but that's the idea.
Let me tell you another perspective.
Is to think of-- but I'm not a particular fan of it.
I think it's a simple idea.
it's really easy to work with.
And so you can pick whichever way you find most intuitive.
in some sense starts at the top of what you want to solve
You could start at the bottom and work your way up.
think about computing Fibonacci numbers
I'm going to write it in a slightly funny way.
I'm doing from the naive recursive algorithm,
is completely automated.
OK.
This code is exactly the same as this code
Just because I needed a couple of different n values here.
And then there's this stuff around that code
A little bit of thought goes into this for loop,
OK.
Maybe it takes a little bit of thinking
here and just write it out sequentially,
This code does exactly the same additions, exactly
The only difference is how you get there.
But the same things happen in the same order.
This code's probably going to be more efficient practice
In fact I made a little mistake here.
just a lookup into a table.
but of course you could use an array.
All right.
I think so.
So we have to compute-- oh, another typo.
And we compute it exactly how we used to.
I know that when I'm computing the k Fibonacci number-- man.
AUDIENCE: [LAUGHTER]
When I compute the kth Fibonacci number
Why?
Nothing fancy.
will just be waiting there.
So I'd know that there's a bug.
I will have always computed these things already.
Then I iterate.
And the one I cared about was the nth one.
So straightforward.
to have to go through this transformation
I'm doing it in Fibonacci because it's super easy
But you can do it for all of the dynamic programs
OK.
This was the special Fibonacci version.
as the memoized version.
of the subproblem dependency DAG.
In order to compute-- I'll do it backwards.
and fn minus 2.
Then there's fn minus 3, which is
So you see what this DAG looks like.
all the edges go left to right.
And so I just need to do f1, f2, up to fn in order.
to solve the subproblems in.
is that we are doing a topological sort.
And usually it's so easy.
Nothing fancy.
I'm missing an arrow.
Let's do something a little more interesting, shall we?
One thing you can do from this bottom-up perspective
Storage space in the algorithm.
but it matters in reality.
n, but in fact we really only need
So you could just store the last two values,
so by thinking a little bit here you
Still linear time, but constant space.
From the bottom-up perspective you
what you need to keep track of.
I guess another nice thing about this perspective
This is clearly constant time.
Whereas, in this memoized algorithm
going to be memoized, when is it not?
just multiply a number of subproblems
But it's a little less obvious than code like this.
All right.
So I'm again, as usual, thinking about single-source shortest
So we want to compute the shortest pathway from s
I'd like to write this initially as a naive recursive algorithm,
I just made that up.
It's not so obvious.
you, here's what you should do.
Actually, it's up to you.
we could figure out how we got there,
Preferences?
All right.
No divine inspiration allowed.
The tool is guessing.
The general idea is, suppose you don't know something
So what's the answer to this question?
Man, I really want a cushion.
Guess.
AUDIENCE: [LAUGHTER]
for solving any problem.
The algorithmic concept is, don't just try any guess.
OK?
PROFESSOR: Also pretty simple.
OK.
This is central to the dynamic programming.
dynamic programming is roughly recursion plus memoization.
Memoization, which is obvious, guessing which is obvious,
I'm trying to make it sound easy because usually people
It is easy.
That's something a computer can do great.
OK.
Not that carefully.
Take the best one.
to be called best.
good for optimization problems.
you try them all and then you can forget about all of them
is the best one, or a best one.
So now I want you to try to apply
Now I'm going to draw a picture which may help.
v. We'd like to find the shortest--
Suppose I want to know what this shortest path is.
You have an idea already?
AUDIENCE: What you could do is you could look at everywhere
[INAUDIBLE] shortest path of each of those notes.
So I can look at all the places I could go from s,
So we could call this s prime.
There's some hypothetical shortest path.
so I will guess where it goes first.
of the outgoing edges from s.
Try them all.
Then from each of those, if somehow I
just do that and take the best choice
So this would be the guess first edge approach.
Not quite the one I wanted because unfortunately
And so this would work, it would just
solving single-source shortest paths.
by guessing the last edge instead of the first edge.
If I was doing this I'd essentially
which we talked about before.
I want to get to v. I'm going to guess the last edge,
I know it's one of the incoming edges to v-- unless s equals v,
As long as this path has length of at least 1,
What is it?
Guess.
recursively compute the shortest path from s to u.
OK.
It's delta of s comma u, which looks the same.
There's v subproblems here I care about. .
I take that.
And that should hopefully give me delta of s comma v.
In reality, I'm not lucky.
So this is the-- we're minimizing
V is already given here.
path from s to u, plus the weight of the edge uv.
the shortest path from s to u.
And wherever the shortest path is, it uses some last edge, uv.
That's the good guess that we're hoping for.
is so we just try them all.
It's going to take the best path from s
paths are shortest paths.
So this part will be delta of su.
So this will give the right answer.
OK.
this is the analog of the naive recursive algorithm
So it's not going to be efficient if I-- I mean,
You could say-- this is a recursive call.
of just a definition.
How good or bad is this recursive algorithm?
PROFESSOR: Terrible.
Very bad, I should say.
without memoization.
We know how to make algorithms better.
OK.
To define the function delta of sv, you first check,
If so return that value.
and then stored it in the memo table.
I don't think I need to write that down.
Just there's now two arguments instead of one.
So I only need to store with v instead of s comma v.
I claim memoization makes everything faster.
Not so obvious, I guess.
How many people think, yes, that's a good algorithm?
PROFESSOR: Better.
Can't be worse.
OK.
How many people aren't sure?
Good.
It's not so tricky.
Something like that.
v. Let me give these guys names, a and b.
that we need to know delta of s comma a and delta
Those are the two ways-- sorry, actually we just need one.
Sorry-- I should have put a base case here too.
OK.
OK.
To compute the shortest path to a we
There's only one.
Now I want to compute the shortest paths from b.
One of them is delta of s comma b-- sorry, s comma s.
The other way is delta of s comma v. Do you see a problem?
Delta of s comma v is what we were trying to figure out.
going to memoize our answer to delta s comma v
Except, we haven't finished computing delta of s
So when this call happens the memo table has not been set.
over and over and over again.
Oops.
So it's going to be infinite time on graphs with cycles.
For DAGs, for acyclic graphs, it actually runs in v plus e time.
In this situation we can use this formula.
times the time per subproblem.
Where's my code?
Number of subproblems is v. There's
I'm always reusing subproblems of the form delta
The something could be any of the v vertices.
That's a little tricky.
to v. So time for a sub problem delta of sv
So this depends on v. So I can't just
What this is really saying is, you
of the time per sub problem.
And we know this is number of edges.
So this is v plus v. OK.
OK.
And it ran a v plus e time.
If you think about it long enough,
doing a depth first search to do a topological sort
So we had topological sort plus one round of Bellman-Ford.
This should look kind of like the Bellman Ford relaxation
It is.
So it's really the same algorithm.
OK.
to solve shortest paths in general graphs, even when they
How am I going to do that?
Lesson learned is that subproblem dependencies
Otherwise, we get an infinite algorithm.
It's all you need.
We've almost seen this already.
you do a topological sort of this subproblem dependency DAG.
OK.
I didn't tell you yet.
For DP to work, for memoization to work, it better be acyclic.
So that's all general.
So somehow I need to take a cyclic graph
We've actually done this already in recitation.
a very simple cyclic graph.
One thing I could do is explode it into multiple layers.
It's like the only cool thing you can do with shortest paths,
If you want to make a shortest path problem harder,
I'm going to do it in a particular way
is to think of this axis as time, or however you want,
to the next layer.
So the idea is, every time I follow
This makes any graph acyclic.
What in the world does this mean?
What does it mean?
All right.
PROFESSOR: So-- I don't know how I've
to double rainbow.
All right.
Delta sub k of sv.
is a new kind of subproblem-- which
s to v path that uses, at most, k edges.
but I also want it to use few edges total.
In some sense, if you look at-- so here's s
And then this is going to be v in the zero situation.
v-- so if I look at this v, I look at the shortest
So maybe I'll call this v sub 0, v sub 1, v sub 2.
Shortest path from here to here is,
Shortest path from here to here, that
Shortest path from here to here--
I guess, cheating a little bit.
to v using at most two edges.
is the min over all last edges.
but realizing that the s to u part uses one fewer edge.
OK.
By adding this k parameter I've made
Unfortunately, I've increased the number of subproblems.
Technically, v times v minus 1.
Sorry.
And what I care about, my goal, is delta sub v minus 1 of sv.
know that I only care about simple paths, paths of length
I'm assuming here no negative weight cycles.
If you assume that, then this is what I care about.
So there are v choices for k.
is v squared.
Well, the same as before.
Up here-- the indegree of that problem.
over all v of the indegree.
total running time is ve.
This is Bellman-Ford's algorithm again.
came from is this view on dynamic programming.
It may seem familiar.
going to see a whole bunch of problems
And that's super cool.