SPEAKER: OK.

So what is dynamic programming?

Normally, of course, I like to ask you to contribute ideas

that we can discuss.

But in this particular case, the point that I want to make

is either you already knew the answer, or you're wrong.

Dynamic programming is designed to be buzzword compliant.

It's something that was invented by Richard Bellman,

and he came up with the name.

And it's actually-- and this is according to his own autobiography--

the problem was that Rand is a defense contractor,

so he was working at Rand, working on computer algorithms,

and Rand worked for the Air Force, and still works for--

it's part of the big industrial military complex--

which meant that their budget depended on ultimately the Secretary of Defense.

And if the Secretary of Defense didn't like what he was doing,

or Congress didn't like what he was doing, and they got wind of it,

that would be the end of it.

So apparently, according to Bellman, the Secretary of Defense at the time

had a pathological aversion to research.

The way he described it is that he would suffuse and become red in the face

if you mentioned the word research in his presence.

And he really didn't like it if you said something like mathematics.

And so Bellman wanted to be sure that whatever he was doing if this showed up

in a Congressional report or in a report that landed on the Department

of Defense's-- on the Secretary of Defense's-- desk,

that it wouldn't say anything objectionable.

So he came up with this term programming, which in the math world,

means optimization-- find the best answer to a problem.

And dynamic and the idea of dynamic, was this

is an adjective that, yes, it sort of expresses that things are changing,

but mostly it has no negative connotations.

Dynamic just sounds good.

So that's where the name comes from.

So dynamic programming is basically a name

that nobody could possibly object to, and therefore

decide to cancel the project.

There is a term that is much more descriptive of what's going on,

which is a lookup table.

So what dynamic programming really is, when it comes down to it,

is it's a way of looking at certain kinds of problems.

With linked data structures, linked lists,

tries, hash tables, all of these sort of fall into a category of data structure

that you use when you've got data and you want

to map the connections between them.

And so there's a whole category of different data structures

that involve using pointers to map the connections between things.

Dynamic programming is a category of algorithms

where you say, in my problem, when I want to solve it,

I end up asking the same question over and over again as part of solving it.

The same question with the same parameters, if you will.

And so rather than doing all the same work over and over again,

let me just remember the answer after I figure it out once,

and the next time I ask the same question,

I'll just go look up what the answer was.

That's the idea of dynamic programming.

And of a lookup table.

You've already used lookup tables.

For example, going way back to the beginning of the class,

Here's a for loop.

for(i=0, i less than strlen of some string variable that I've called str,

i++.

this.

Is a loop the loop through every character

of this string, str, one by one.

But the problem is every time you go through the loop,

you recalculate the length of this string.

And calculating the length of the string in C

takes some time because you have to walk down the whole string until you

reach that null character at the end.

So going all the way back again to the beginning of the class,

remember, we talked about, it would be better from a performance perspective

not to keep recalculating the length of the string.

Instead, why not say something like int length=strlen(str),

and save that value to a variable, and just look up that value every time we

go through the loop and are checking-- have we reached the last value of i?

There, length you can think of as a lookup table that stores one value.

There's already an example that you've seen.

We're going go to lookup tables that store

the answer to more than one thing.

And so I'm going to go through today a few different examples of problems

that you can solve using dynamic programming.

So these are problems where you can break them down in a way

that you keep asking the same question over and over again

and just look up the answer in a table or an array.

And the first such problem I want to talk about is rod cutting.

Now the idea of this is I have a rod of something valuable,

so maybe it's a Tootsie Roll, or plutonium,

there's a wide range of things that come as sort of like a long cylinder.

And you want to chop it up into shorter pieces to sell.

And what you know is that different length pieces, different length rods,

sell for different amounts.

And the question is, how should I cut this long thing up

into smaller pieces to maximize the money that I can sell it for?

So if I know, for example, that a rod that's one inch long sells for $1,

and a rod that's two inches long turns out to be a lot more valuable,

I can sell that for $5.

And when it's three inches long I can sell for $8.

Now there's a lot more demand for things that are three inches long

then things that are four inches long.

So if it's four inches long, I can sell it

for $9, which is a little more but not a lot more.

And then comes the question--

I've got a rod of length 10--

how should I chop it down into 1s and 2s and 3s and 4s to maximize the profit.

And there's different ways I could do this.

I could chop it into 10 little one inch rods, and sell each one for $1

and I've made $10.

I could chop it into five two inch rods, and it would get 5 times 5 is $25.

That's a lot more money.

So being the unabashed capitalist than I am, that's what I'm likely to do.

And there are some in-between options that might make me some money.

The question is, how to quickly figure out

what I should chop this rod into to maximize my profit

and be sure that that's the most that I can sell it

for There wasn't some other way to chop this up that would be better.

And one way to think about the problem is,

if I've got a rod that's 10 inches long and I can chop it once an inch,

there are 1, 2, 3, 4, 5, 6, 7, 8, 9 possible places I could cut the rod.

And any one of those places I could either decide to make a cut

or not make a cut.

And that will affect the end result.

So that's kind of 9 bits--

I either cut or I don't.

They're a 1 or a 0.

So I end up in terms of the possible different combinations

of how I could cut this with every possible 9-bit number

in binary, which has 2 to the 9th possible values, which is 512.

So I could try 512 possible different ways to cut this rod.

And I can figure out which one does the best.

And then I could try having a rod that was 20 inches long instead,

and discover there's 19 possible places to decide I'm going to cut it

or I'm not, and there's 2 to the 19th possibilities

now, which is about 500,000.

2 to the 10th is about 1,000, 2 to the 20th is about a million, 2 to the 19th

is about a million divided by 2, it's about 500,000.

So in general, if we said this rod is n inches long,

so that there's n places or n minus 1 places where I could make a decision

to cut it, there are 2 to the n approximately possible different ways

of making combinations of cuts.

And that's a lot of things to try.

At the same time, you can sort of see that splitting it into rods

of 1, 1 5, 5, and 9 inches long--

this is not the only combination of cuts that would give me that.

There are other combinations that would also give me two 1s, two 5s, and--

sorry, a 4 inch long.

Two 1s, two 2s, and a 4.

I could do a 4 and then two 2s and then two 1s.

I'd get the same value out of it.

So a lot of the possible ways that we could cut--

they would give the same result in terms of the value.

And so maybe I want to reorganize the problem

where I don't have to try everything, because I realize a lot of times

I'm just recalculating the same thing.

And one way to do that--

and this is where this concept of dynamic programming or a lookup table

comes in--

is to say, let me decide first where to cut where the left most cut will be.

So instead of deciding, am I going to cut it 1 inch or not,

am I going to cut it 2 inches or not, am I going to cut it 3 inches or not,

I'm going to decide what's the first place that I'm going to cut?

That could be at 1 inches or 2 inches or 3 inches or 4 inches

or 5 inches or 6 or 7 or 8 or 9 inches, or I

could decide I'm not going to cut at all,

I'm just going to leave the rod whole.

So with his rod of length 10, there's 10 possible places to make the first cut.

And the thing that I'm going to decide is that that splits the rod into two--

the part on the left I'm not going to cut again.

I'm not going to cut this 2 part--

or the 3 part--

I'm making that decision.

This is the first piece that I'm going to sell.

So the total value that I can get will be

whatever I can sell the piece on the left for like $1 or $5 or $8 or $9,

plus whatever I can get for the right part if I chop it into smaller pieces

the best possible way.

So the part on the left I won't cut again.

I can just look up what is the value of a rod of this length in the table.

But I also need to figure out for the part on the right, what

is the best way to cut this up.

And even that, if you draw out all the possibilities,

you're going to end up with the same 2 to the n,

except you can start seeing some commonalities.

So for example, if you decided to cut a rod of length 2,

you've got eight leftover, and you want to find the best way to cut it.

Now, if you only chopped off one inch first, that was your first cut,

and then you did another cut where you chopped off another inch,

suddenly you're end up with what is the best way to cut a rod of length eight.

So in the possible ways of chopping this thing of length 9,

one possibility is, again, we take one inch off to sell,

and we have eight inches left.

If right from the start we've taken two inches off,

we would also have eight inches left.

And so we're asking the same question both times.

We've said, I've got some stuff I've already cut that I'm going to sell,

and now I've got an eight inch rod left.

How do I cut that?

There's no point figuring that out twice.

We could just keep a little array in which we store, what's

the best way to cut a rod of length 8?

What's the best way to cut around of length 9, of 7, 6, of 5,

of 4, and for each one of those, we just look in the array and say,

have we put a value in there yet?

If so, we just use it.

We don't recompute it.

And the result is, if you start looking at it,

we've got 10 choices for our first cut, and then on average we've

got something like up to nine choices for our second cut,

and up to eight choices for our third cut.

And so for each of the possible 10 choices the first time,

we've got nine choices to make for our second cut, we're up to 90.

But this would get us exponential.

The problem is a lot of these cuts end up being the same.

And so you end up saying, I only have to deal

with sort of 10 choices of what to make as the first cut for right of length

10, and nine choices to make for the first cut of a rod of length 9,