# 20. Dynamic Programming II: Text Justification, Blackjack

The following

content is provided

under a Creative

Commons license.

Your support will help MIT

OpenCourseWare continue

to offer high quality

educational resources for free.

To make a donation or

view additional materials

from hundreds of MIT courses,

visit MIT OpenCourseWare

at ocw.mit.edu.

PROFESSOR: All right, today we

continue our exciting adventure

into dynamic programming.

Are you excited?

I’m excited, super excited.

Dynamic programming,

as you recall way back

before Thanksgiving, is a super

exciting powerful technique

to design algorithms, especially

to solve optimization problems

where you want to maximize

or minimize something.

Last time, we saw how

two algorithms we already

knew– namely, how to compute

the nth Fibonacci number

and how to compute shortest

paths via Bellman-Ford–

are really dynamic

programs in disguise.

And indeed for, at

least for Bellman-Ford,

that’s how they

were invented, was

to apply a general

technique which

we’re going to see today

in full generality,

more or less– most of

this is generality–

in five easy steps.

And we’re going to see

that technique applied

to two new problems

which are much more

interesting than the ones

we’ve already solved– namely,

how to make your text

look nice in a paragraph,

where to break the lines.

That’s text justification.

And how to win and make

loads of money at blackjack.

So lots of practical

stuff here, and we’re

going to see one

new technique for

general dynamic programming.

These are some things

I wrote last time.

Actually, one of them I

didn’t write last time.

In general, you can think

of dynamic programming

as a carefully executed

brute force search.

So in some sense,

your algorithm is

going to be trying

all the possibilities,

but somehow avoiding

the fact that there

are exponentially many of them.

By thinking of it

in a clever way,

you can reduce the

exponential search space

down to a polynomial one,

even though you’re still

not being very intelligent

you’re still blindly trying

all possibilities.

So that’s the brute force part.

In more detail, the

three main techniques

in dynamic programming are

the idea of guessing, the idea

that, oh, I want to find the

best way to solve a problem.

Let’s pick out some

feature of the solution

that I want to know.

I don’t know it, so

I’ll guess the answer–

meaning I’ll try all the

possibilities for that choice

and take the best one.

So guessing is really central

to dynamic programming.

Then we also use a

recursion, some way

to express the solution to our

problem in terms of solutions

to sub-problems.

So it’s usually very

easy to get a recursion

for a lot of problems

as long as they

have some kind of substructure.

Like shortest paths, we had that

some paths of shortest paths

were also shortest

paths, so that was handy.

Usually the recursion by

itself is exponential time,

like even with

Fibonacci numbers.

But we add in this

technique of memoization,

which is just once we compute an

answer we’ve stored in a lookup

table, if we ever

need that answer again

we reuse it instead

of recomputing it.

So we store it.

We write down in our memo

pad anything that we compute.

Those techniques, all

these techniques together

give you, typically,

a polynomial time

dynamic program– when

they work, of course.

Memoization makes the

recursion polynomial time.

The guessing is what is

doing a brute force search.

And magically, it all

works if you’re careful.

Another perspective– kind

of an orthogonal perspective

or another way of thinking

about it, which I think

should be comfortable

for you because we

spent a lot of time

doing shortest paths

and expressing problems that we

care about in terms of shortest

paths even if they don’t look

like it at first glance–

dynamic programming

in some sense

is always computing

shortest paths in a DAG.

So you have some problem

you want to solve,

like you have text you want to

split up into lines so it looks

nice in a paragraph, you

express that problem somehow

as a directed acyclic graph.

And then we know how to

compute shortest path

in directed acyclic

graphs in linear time.

And that’s basically what

dynamic programming is doing.

I didn’t realize

this until last week,

so this is a new perspective.

It’s an experimental

perspective.

But I think it’s helpful.

It’s actually– dynamic

programming is not that new.

It’s all about how to be

clever in setting up that DAG.

But in the end, the

algorithm is very simple.

And then we had this

other perspective–

back to this

perspective, I guess.

In general, we have– the

real problem we want to solve,

we generalize it in some

sense by considering

lots of different sub-problems

that we might care about.

Like with Fibonacci, we had

the nth Fibonacci number.

We really just wanted

the nth Fibonacci number.

But along the way, we’re going

to compute all f1 up to fn.

So those are our sub-problems.

And if we compute

the amount of time

we need to solve

each sub-problem

and multiply that by the

number of sub-problems we get,

the total time required

by the algorithm.

This is a general true fact.

And the fun part here is we get

to treat any recursive calls

in this recursion as

free, as constant time,

because we really only

pay for it first time.

That’s counted out here.

The second time we call

it, it’s already memoized,

so we don’t have to pay for it.

So this is, in some

sense, an amortization,

if you remember amortization

from table doubling.

We’re just changing

around when we

count the cost of

each sub-problem,

and then this is the

total running time.

OK, so that’s the

spirit we saw already.

I’m going to give you

the five general steps,

and then we’re going to apply

them to two new problems.

So five easy steps to

dynamic programming.

Unfortunately, these are not

necessarily sequential steps.

They’re a little

bit interdependent,

and so “easy”

should be in quotes.

This is how you would

express a dynamic program,

and in some sense

how you’d invent one,

but in particular how

you would explain one.

OK, let me get to

the main steps first.

First step is to figure out

what your sub-problems are

going to be.

Second part is to

guess something.

Third step is to relate

sub-problem solutions, usually

with a recurrence.

I guess always

with a recurrence.

Fourth step is to actually

build an algorithm.

And we saw two ways

to do that last time.

One is to use recursion

and memoization, which

is the way I like

to think about it.

But if you prefer, you can

follow the bottom up approach.

And usually that’s

called building a table.

And that one’s basically to turn

our recursion and memoization,

which is kind of

fancy, into a bunch

of for loops, which

is pretty simple.

And this is going to be more

practical, faster, and so on.

And depending on your

preference, one of them

is more intuitive

than the other.

It doesn’t matter.

They have the same running

time, more or less,

in the worst case.

Then the fifth step is to

solve the original problem.

All right, so we’ve sort

of seen this before.

In fact I have, over

here, a convenient table.

It’s called cheating.

The two problems we saw

last time, Fibonacci numbers

and shortest paths.

And I’ve got steps

one, two, three,

four– I ran out of room,

so I didn’t write five yet.

But we’ll get there.

So what are our sub-problems?

Well, for Fibonacci,

they were f1 through fn.

So there were n

different sub-problems.

And in general because

of this formula,

we want to count how many

sub-problems are there.

So number of

sub-problems is– this

is what we need to

do algorithmically.

And then for analysis,

we want to counter

number of sub-problems

for step one.

And so for Fibonacci

there were n of them.

For shortest paths, we defined

this delta sub k of sv.

This was the

shortest path from s

to v they uses at most k edges.

That was sort of what

Bellman-Ford was doing.

And the number of

different sub-problems

here was v squared, because we

had to do this for every vertex

v and we had to do it for

every value of k between 0

and v minus 1. v minus was

is the number of rounds

we need in Bellman-Ford.

So it’s v times v,

different sub-problems,

b squared of them.

OK, second thing was we

wanted to solve our problem.

And we do that by guessing

some feature of the solution.

In Fibonacci, there

was no guessing.

So the number of different

choices for your guess is one.

There’s nothing.

There’s only one choice,

which is to do nothing.

And for shortest paths,

what we guessed was–

we know we’re looking for some

path from s v. B Let’s guess

what the last edge is.

There’s some last

edge from u to v,

assuming the path has more

than one edge– or more

than zero edges.

When could the edge possibly be?

Well, it’s some

incoming edge to v.

So there’s going to be

indegree of v different choices

for that.

And to account for the case that

that’s zero, we do a plus 1.

But that’s not a big deal.

So that was the number

of different choices.

In general if we’re

going to guess something,

we need to write down

the number of choices.

For the guess, how many

different possibilities

are there?

That’s our analysis.

OK, the next thing

is the recurrence.

That’s step three.

We want to relate all

the sub-problem solutions

to each other.

For Fibonacci,

that’s the definition

of Fibonacci numbers.

So it’s really easy.

For shortest paths,

we wrote this min.

In general, typically

it’s a min or a max,

whatever you’re

trying to solve here.

We’re doing shortest paths.

You could do longest

paths in the same way.

So you compute them in of

delta sub sk minus 1 of su.

The idea is we want to compute

this part of the path, the s

to u part.

And we know that has one

fewer edge, because we just

guessed what the last edge was.

Except we don’t really know

what the last edge was,

so we have to try them all.

We try all the incoming edges

into v– that’s this part–

and for each of

them we compute–

I forgot something here.

This is the cost of the

first part of the path.

Then I also need to do plus

the weight of the uv edge.

That will be the total

cost of that path.

You add those up, you do

it for every incoming edge.

That is, in some sense,

considering all possible paths.

Assuming you find the

shortest path from s to u,

that’s going to be the

best way to get there.

And then use some edge from

u to v for some choice of u.

This will try all of them.

So it’s really trying

all the possibilities.

So it’s pretty clear

this is correct

if there are no

negative weight cycles.

You have to prove some things.

We’ve already proved them.

It’s just slow, but once you

add memoization, it’s fast.

Now, how long does it take

to evaluate this recurrence,

constant time, if you

don’t count the recursive

calls or count them as constant?

Over here, we’re taking a min

over n degree of v things.

So we have to pay

n degree of v time,

again the recursions as free.

But for each one of them,

we have to do an addition.

So it’s constant work per guess.

And this is quite common.

Often, the number of

guesses and the running time

per sub-problem are the

same, the constant factors.

Sometimes they’re different.

We’ll see some examples today.

OK, step four.

Let’s see.

So here we evaluate the

time per sub-problem.

Once you have the recurrence,

that becomes clear.

You want to make sure

that’s polynomial.

Often these are the same.

And then we add the recursive

memorize or build a DP table.

I’m not going to write those.

We did it for Fibonacci

last time, shortest paths.

Pretty easy.

And in general, what

we need to check here

is that the sub problem

recurrence is acyclic.

In other words, that it

has a topological order so

we can use topological sort.

We don’t actually use

topological algorithm usually.

You can just think about it.

In the case of

Fibonacci numbers,

it’s clear you want to

start with the smallest one

and end up with the biggest one.

You can’t do the reverse,

because then when

you’re trying to computer the

nth you don’t have the ones

you need, the n minus

1 and n minus 2.

But if you do it in

this order, you always

have the one you need by

the time you get there.

In general, there’s

a DAG there–

and for Fibonacci,

it was like this.

Every node depends

on the previous

and the second previous.

But you just choose

a topological order,

which is here left to

right, and you’re golden.

And these are

actually the for loops

you get in the bottom of DP.

For shortest paths, you

have to think a little bit.

You have to do the for

loop over k on the outside,

the for loop over

V on the inside.

The reverse does not work.

I won’t go through that, but

we drew the DAG last time.

And that’s the main thing

you need to do here.

And then, of course,

you use this formula

to compute the overall running

time, which is just multiplying

this quantity with

this quantity.

Total time.

Then there’s just

one last step that

usually isn’t that big a deal,

but you have think about it.

You need to make sure that

the problem you actually

cared about solving gets solved.

In the case of Fibonacci

and shortest paths,

this is pretty clear.

I didn’t write it.

We can do it on here.

Solve the original problem.

Fibonaci, it is Fn.

And this is one of

our sub-problems,

so if we solve all

of them, we’re done.

For shortest paths,

it’s basically

delta sub v minus 1 of

sv for all v. That’s

single source shortest paths.

And by our

Bellman-Ford analysis,

that gives us the

right shortest paths.

There are no negative

weight cycles.

And sometimes this

requires extra time

to combine your solutions

to get the real thing.

Here of course, we just have the

answers, so writing them down

does not take very long.

So that’s the dominant running

time– which I didn’t write,

I should have written in

under for here– this ends up

being n, this ends up being VE.

OK, I don’t want to spend

more time on those examples.

Let’s go to new things.

So first problem we’re

going to look at today

is text justification.

And the informal

statement of this problem

is you’re given

some text– which

means a string, a whole

bunch of characters.

And we want to split

them into good lines.

The rules of the game

here are we’re going to,

like in the early lectures

of document distance

where you have some

definition of splitting

a document into words

separated by spaces.

And what we want to do is cut.

We can only cut between

word boundaries.

And we want to write

some text, it’s

going to have some spaces in it.

Then there’s a new line,

something like that.

And we want to justify our

text on the right here.

And so we’d like to avoid big

gaps like this because they

look ugly, they’re hard to read.

Now, if you use

Microsoft Word– at least

before the latest

versions– they

follow a greedy strategy,

which is very simple.

You pack as many words as

you can on the first line,

then you go to the next

line, pack as many words

as you can on the second line.

Keep going like that.

And that strategy

is not optimal.

If you use LaTeX–

as some of you

have been doing on problem sets,

and I think also new versions

of Word but I’m

not sure– then it

uses dynamic programming

to solve this problem.

And that’s what we’re

going to do here.

So let me specify a little bit

more about what we mean here.

So the text we’re going to

think of as a list of words.

And we’re going to define

a quantity badness.

And this is an anesthetic

quantity, if you will.

I’m going to tell

you what LaTeX uses.

But this is sort

of how bad it is

to use– or let’s say, yeah,

words i through j as a line.

So this is python notation.

So it starts at i and

ends at J minus 1.

That’ll be convenient.

So I have this list of words.

And if I look at words

i through j minus 1

and I think of what happens if

I pack them in a line, well,

they may fit or

they may not fit.

So there are going

to be two cases.

If they don’t fit, I’m

going to write infinity.

So that’s really bad.

So I have some notion of

how wide my line can be.

And if the sum of the lengths

of those words plus the sum

of the lengths of the

spaces as small as possible

is bigger than the width

of my screen– or page,

I guess– then I

say they don’t fit,

and then I define badness

to be infinity– meaning,

I never want to do that.

This is actually

LaTeX sloppy mode,

if you want to be technical.

Otherwise, it’s going to be page

width minus total width cubed.

Why cubed?

Who knows.

This is the LaTeX rule.

And squared would

probably also be fine.

So this is the width of the

page minus the total width

of those words,

which you also have

to include the spaces here.

You take the difference.

You cube it.

And so when this

is small– I mean,

when these are very

close– then this

is going to be close to zero.

That’s good.

That means you use

most of the line.

When the total width is much

smaller than the page width,

then this will be a large value.

You cube it, it

will be even larger.

So this will highly

discourage big gaps like this.

And it will very much

discourage not fitting.

So there’s a

tradeoff, of course.

And the idea is you might–

in the greedy algorithm,

you make the first line

as good as you can.

But it might actually

be better to leave out

some of the words

that would fit here

in order to make the

next line better.

In general, it’s hard

to tell, where should I

cut the lines in order to get

the best overall strategy?

What I’d like to

minimize is the sum

of the badnesses of the lines.

So it’s a sum of cubes,

and that’s really hard

to think about.

But that’s what dynamic

programming is for.

You don’t have to think.

It’s great because

it’s brute force.

OK, so the first thing we need

to do is define sub-problems.

This is, in some

sense, the hard part.

The rest will follow easily.

So I think actually

it might be easier

to think about, for

this problem, what

would be the brute

force strategy?

How would you try all

possibilities, exponential

time?

Suggestions?

Yeah?

AUDIENCE: Try all partitions

of the words that don’t fit?

PROFESSOR: Try all

partitions of the word,

so– of the string of words.

So I mean, it could be it

all fits in on one line.

It could be it’s

split into two lines.

I try all possible splits there.

In general, I’m

guessing for every word,

does this start a line or not?

That would be all ways.

And so there are 2 to the n.

If I have n words, there’s

2 to the n different splits.

For every word I say yes or

no, does this is begin a line?

So what I’d like to figure out

is where those lines begin.

That was the point

of that exercise.

So any suggestions?

Maybe it’s actually easier

to jump ahead and think,

what would I guess

in my solution

if I have this big

string of words?

What’s the natural

first thing to guess?

Yeah?

AUDIENCE: Guess how

long the first line is?

PROFESSOR: Guess how long

the first line is, yeah.

We know that the first

word begins a line.

But where does the

second line begin?

So I’d like to guess where

the second line begins.

That’s– so you know, I have

the beginning of a line here

and then I have a beginning of

a line here at the fourth word.

Where does the

second line begin?

I don’t know.

Guess.

So I’m going to try

all the possible words

after the first word.

And say, well, what if I

started my second line here?

At some point I’m

going to be packing

too much into the first

line, and so I abort.

But I’ll try them all.

Why not?

OK, that’s good.

The issue is that

once I’ve chosen

where the second line is, of

course the next thing I want

to guess is where the

third line begins.

And then I want I guess

where the fourth line begins,

and so on.

In general, I need to

set up my sub-problems

so that after I

do the first guess

I have the problem

of the original type.

So originally I

have all the words.

But after I guess where

the second line begins,

I have the remaining words.

What’s a good word for

the remaining words?

If I give you a list of words

and I want from here on,

it’s called– what?

A sub-problem, yes.

That’s what we want to define.

It’s called a

suffix of the array.

That’s the word I

was looking for.

It’s tough when I only

have one word answers.

So my sub-problems are

going to be suffixes.

Which is, in python

notation, i colon.

They call it splices.

And how many sub-problems

are there if I have n words?

Two?

Sorry?

AUDIENCE: 2 to the n.

PROFESSOR: 2 the n?

That would be a problem

if it’s 2 to the n.

I hope it’s only n.

Originally, we said, OK, for

every word, we’re going to say,

is this in our out?

Is this the beginning or not?

That’s 2 to the n.

But here, the idea is we’re

only thinking about, well,

what are the words that remain?

And it could be you’ve dealt

with the first 100 words

and then you’ve got

n minus 100 left,

or it could be you’ve dealt

with the first thousand words

and you’ve got n minus 1,000.

There’s only n choices for that.

We’re only remembering

one line, this is the key.

Even though we may have

already guessed several lines,

we’re just going to

remember, well, OK.

This is what we have left to do.

So let’s forget about the past.

This is what makes dynamic

programming efficient.

And we’re just going to solve

it, solve these sub-problems,

forgetting about the past.

So the sub-problem–

I’m not going

to write it here– is if

I give you these words,

never mind the other words,

how do I pack them optimally

into a paragraph?

I don’t care about the other

words, just these words.

So this is a different

version of the same problem.

Initially, we have

n words to do.

Now I have n minus

i words to do.

But it’s again

text justification.

I want to solve this

problem on those words.

That’s just how I’m

going to define it.

This will work if I can

specify a recurrence relation.

As we said, what

we guess is where

to break the first

line, where to start

the second line for those words.

OK, so this is– it could

be the i plus first line.

It could be the i plus

second line– or sorry, word.

Some word after i is where

we guess the second word.

The number of choices for the

guess is at most n minus i.

I’m just going to think

of that as order n.

It won’t matter.

The third part is we need

a recurrence relation.

I claim this is very easy.

I’m going to– I didn’t

give this problem a name,

so I’m just going to

write it as DP of i.

So this is going to be the

solution to that suffix, words

from i onward.

And I’d like to–

what I want to do

is consider all

possible guesses.

So I mean this is going to be

pretty formulaic at this point.

After I’ve set up these

ideas there’s pretty much

only one thing I can

write here, which

is I want to do a for loop.

That would be the

for loop of where

the second line can start.

I can’t start at

i, because that’s

where the first line starts.

But it could start at i plus 1.

And this special

value of n will mean

that there is no second line.

OK, so DP of i– now I

want to do this for loop

in order to try all

the possible guesses.

j will be the word where

the next thing starts.

So then what do I write up here?

If I make this guess–

all right, so I have word

i is the first word

of the first line.

And then word j is the first

word of the second line.

And then there’s more

stuff down below.

I don’t know what that is.

But how can I use

recursion to specify this?

DP of j, exactly.

I guess if I’m

doing recursion, I

should use parentheses

instead of brackets.

But if you’re

doing it bottom up,

it would be square brackets.

So that’s just DP of j.

That’s the cost of the

rest of the problem.

And I can assume that

that’s free to compute.

This is the magic of

dynamic programming.

But then I also have

to think about, well,

what about the first line?

How much does that cost?

Well, that’s just badness of ij.

And we’ve already defined that.

We can compute it

in constant time.

Dynamic programming doesn’t

really care what this is.

It could be anything.

As long as you’re

trying to minimize

the sum of the badnesses,

whatever function is in here,

we just compute it here.

That’s the power of

dynamic programming.

It works for all

variations of this problem,

however you define badness.

So you might say, oh,

that’s a weird definition.

I want to use

something else instead.

That’s fine, as long

as you can compute it

in terms of just i and j

and looking at those words.

OK, now I need to do a

min over the whole thing.

So I want to minimize

the sum of the badnesses.

So I compute for

every guess of j,

I compute the cost of

the rest of the problem

plus the cost of

that first line.

And this, is in some sense,

checking all possible solutions

magically.

OK.

That’s the recurrence.

We need to check some things.

I guess right now we just want

to compute how much time does

this cost, time per sub-problem.

To do this for loop, basically

I do constant work– all of this

is constant work–

for each choice.

So there’s order n choices,

so this is order n.

Now we have to

check that there’s

a topological order

for this problem

or for these sub-problems.

And this is easy, but

a little different

from what we’ve done

before because we

have to actually work

from the end backwards,

because we’re expressing

DP of i in terms

of DP of larger values of i.

j is always bigger than i.

And so we have to do it

from the right end back

to the beginning.

And n minus 1 down to 0.

I didn’t actually

define DP of n.

There’s a base case here

which is DP of n equals 0.

Because the meaning of DP

of n is I have zero words,

the nth word onward.

There is no nth word.

It’s 0 to n minus

1 in this notation.

So I don’t pay anything

for a blank line.

OK, so that’s our

top logical order.

This one, of course,

is instantaneous.

And then we work backwards.

And always whenever we

need to compute something,

we already have the value.

The total time we

get is going to be

the number of sub

problems– which

is n times the running

time per sub-problem.

which is order n, which

is order n squared.

And in the worst case, it

is indeed theta n squared.

Although in practice it’s going

to work better, because lines

can’t be too long.

So that’s the running time.

Then finally we have to check

that the original problem

actually gets solved.

And in this case, the original

problem we need to solve

is DP of 0 because DP of 0 means

I take words from 0 onwards.

That’s everybody.

So that’s the actual

problem I want to solve.

So we work backwards.

We solve all these sub-problems

that we don’t directly

care about, but then the

first one is the one we want.

And we’re done.

So in quadratic time,

we can find the best way

to pack words into lines.

Question?

AUDIENCE: [INAUDIBLE]

PROFESSOR: DP of j is returning.

It’s like this.

So DP of– this is a

recursive definition.

Imagine this is a

recursive function.

I wrote equals, which is

Haskell notation, if you will.

But normally, you think of

this as like def DP of i

is return min of this.

This is python.

So it’s returning the cost.

What was the best way to pack

those lines from j onwards?

That’s what DP of j returns.

So it’s a number.

It’s going to be a

sum of badness values.

Then we add on one

new badness value.

It’s still a sum

of badness values.

We return the best

one that we find.

Now, this does not

actually pack the words.

That’s a good– maybe

your implicit question.

It’s not telling you

how to pack the words.

It’s telling you how much

it costs to pack the words.

This is a lot like shortest

paths where we didn’t– it was

annoying to actually figure

out what the shortest path was.

Not that annoying,

but that’s not

what we were usually

aiming to do.

We were just trying to figure

out the shortest path weight.

And then once we knew

the shortest path weight,

it was pretty easy to

reconstruct the paths.

So maybe I’ll take a

little diversion to that

and talk about parent pointers.

The idea with parent

pointers is just

remember which guess was best.

it’s a very simple idea, but it

applies to all dynamic programs

and lets you find the

actual solution, not just

the cost of the solution.

We did the same thing

with shortest paths.

We even called them parent.

So when we compute this min,

were trying all choices of j.

One of them– or maybe more than

one, but at least one of them

actually gave you the min.

That’s usually called the

arg min in mathematics.

It’s what was the value

of j that gave you

the minimum value of this thing.

So I mean, when you

compute the min,

you’re iterating over

every single one.

Just keep track of

which one was the best.

That’s it.

Call that the parent pointer.

Do I need to write that?

Here, parent–

parent of i is going

to be arg min of

that same thing.

So it’s a j value.

It’s the best j value for i.

And so we store that for each i.

It cost no more work,

just a constant factor

more work than

computing the min.

We also write down the arg min.

So we’re already storing

the min in the DP table.

DP of i would get

sorted to be that.

We also store parent of i.

And then once we’re done, we

start with our original problem

and we follow parent

pointers to figure out

what the best choices were.

So we start at 0 because we

know word zero begins a line.

And then 0 will

be the first line.

Then we go to parent of 0.

That will be where the

second line begins.

Then we go to parent

of parent of 0.

That will be where

the third line begins.

OK, because these

were the best choices

for where the

second line begins,

this is the best place where

the second line begins.

Given that this

is the first line,

this is the best line where

the second line begins

given that this

was the first line.

So that’s really the third line

given this was the second line.

Little confusing, but you

just a simple for loop.

You start with 0 because

that’s our original problem.

You keep calling parent of

the thing you currently have.

In linear time, you

will reconstruct

where the lines break.

So you can use this

technique in any DP.

It’s very simple.

It’s totally automatic.

Just like memoization

is a technique

that you can apply

without thinking,

you could even write a program,

given a recursive algorithm,

would turn into a memorized

recursive algorithm.

It’s totally automated.

Same thing with the

bottom up DP table.

As long as you know what

the topological order is,

just make those for

loops and then put

exactly the recursive call but

turn it into an array call.

Boom, you’ve got a

bottom up algorithm.

Totally automatic,

no thinking required.

Parent pointers also,

no thinking required.

As long as you’re following

the structure of trial guesses

compute some value–

just remember

what the guess was– you

reconstruct your solution.

That’s the great thing

about dynamic programming

is how much of it is automatic.

The hard part is figuring

out what to guess

and then what your sub-problems

are, or the other order.

Whatever works.

Any other questions about text?

I would like to move

on to blackjack.

OK, now I brought some

cards, because some of you

may not know the

rules to blackjack.

How many people know blackjack?

OK.

How many people do not and

are willing to admit it?

A few, all right.

So this is for you and

for fun, entertainment.

So I’m going to bring Victor

up to help demonstrate

the rules of blackjack.

We’re going to play

standard Casino blackjack

as in the movie 21, or whatever.

So I’m going to just do a random

cut here so I can’t sheet.

You have a tablet, that’s scary.

You’re going to

look at strategy.

VICTOR: Nothing special.

PROFESSOR: All right.

Hopefully you do not

have x-ray vision.

So the way it works

is there’s a dealer

player and one or more players.

We’re just going to do it with

one player to keep it simple.

I’m going to be the dealer.

So my strategy is actually

totally deterministic,

there’s nothing interesting.

Victor has the hard

part of winning.

So to start out, I believe

we deal to you first, then

to me, then to you, then to me.

So let’s hold up

these cards, Victor,

so that people can see them.

You don’t get to

see one of my cards.

That’s some peculiarity

of the rule.

And if the sum of our cards

goes over 21, we lose the game.

Victor first.

I cannot have a value more

than 21 in these hands,

because I only have two cards.

You have a value of– ha, ace.

Great.

An ace can be a 1 or an 11.

That’s the fun rule.

So this is either an 8 or an 18.

And so Victor has a choice of

whether to take another card

or not.

What would you like to do?

VICTOR: Standard

strategy says stand.

PROFESSOR: He stands.

So he’s going to stick to that.

At this point, my

cards flip over.

I have 17, which

is same you, which

I believe means– I

forget about tie rules.

VICTOR: I have 18.

PROFESSOR: You have 18.

All right.

VICTOR: See?

The strategy works.

PROFESSOR: So that’s good.

I’m going to hit in the hope

that I have a small card that

will push me right above you.

But I do not.

I lose.

I’m sad.

VICTOR: It says

always stand on a 17.

PROFESSOR: Oh,

always stand on 17?

Huh.

All right, never mind.

Thanks.

Yeah, I still lose.

The game is over.

My strategy is always

stand on a value–

VICTOR: Stand on 17.

PROFESSOR: 17 or higher.

And if I have a value less than

17, I always take another card.

So let’s do it one more

time to get it right.

So I’m going to deal to you,

deal to me, deal to you,

deal to me.

So hold up your cards.

You have 18 again.

Are you cheating?

VICTOR: I still have to stand.

PROFESSOR: You still

stand, according to tablet.

So I, in this case, have a 20.

And so this I win.

So you get the idea.

Let’s say in each

case we’re betting $1.

So at this point, we’d be even.

He won $1, I won $1.

But in general, slight–

I think it’s balanced.

VICTOR: For these rules, there’s

a 1% advantage for the house.

PROFESSOR: 1% advantage

for the house.

Interesting.

All right, well, that’s

beyond this class.

What we’re going to see is

how to cheat in blackjack.

So this is going to be– I

encourage you to try this out

at casinos.

Just kidding.

This is a little bit difficult

to actually do in a casino

unless you have an inside man.

So if you have an

inside man, go for it.

It’s guaranteed to

win you lots of money

because it’s going

to play optimally.

In perfect

information blackjack,

I suppose that I already

know the entire deck.

Suppose somehow either I

get to put the deck there,

or I have some x-ray vision.

I get to see the entire

deck ahead of time.

And then somebody’s

going to play

through a game over and over

with me– or not over and over,

but until the deck

is depleted– and I

want to know in each

case, should I hit,

or should I stand?

And I claim with

dynamic programming

you can figure that out–

using exactly the same strategy

as text, actually.

It’s really for

each word, should I

start a new line or not?

Same problem here.

It’s slightly more

complicated to write down.

So let’s say the deck

is a sequence of cards.

And I’m going to call it c0,

c1 up to cn minus 1, n cards.

And you are one player.

First is the dealer.

I don’t know how to

solve this for two

players, interesting

open problem.

But for one player I can do it.

Let’s say $1 bet per hand,

I think they’re called.

I’m not sure.

Per play?

Per box?

Whatever.

You’re not allowed to double.

You’re not allowed to split.

All these fancy rules are

harder to think about,

although you might be able

to solve them as well.

So the idea is I

have some cards.

Should I hit or should I stand?

I don’t know.

I’ll guess.

So our guessing– let’s jump

ahead to the guessing part–

is whether we want to hit

or stand given a card.

Actually, it would

be easier to think

about an entire

play, an entire hand.

We’re going to guess,

how many times should I

hit in the first play?

So initially, four

cards are dealt.

I look at my hands.

Actually, I don’t

really look at my hand.

I’m just going to

guess ahead of time.

I think I’ll hit

five times this time.

I think I’ll hit

zero times this time.

I mean, I’m just

going to try them all.

So I don’t really have to

be intelligent here, OK?

It’s kind of crazy but it works.

Our sub-problems,

can anyone tell me

what our sub-problems would

be, In one word or less?

Less would be impressive.

Yeah?

AUDIENCE: Where you

start the new hand.

PROFESSOR: Where do

you start the new hand?

Yeah.

So it’s going to be

suffixes of the cards.

So at some point we do a play,

and then we get to ith card.

And then the rest of the game

will be from the ith card on.

So it’s going to

be suffix ci colon,

I guess would be

the notation here.

It’s a bit awkward.

These are the cards that remain.

And so the sub-problem

is, what is the best play?

What’s the best

outcome given $1 bets?

How much money can I make–

maximize my winning, say–

given these cards onward?

Who knows what happened to

their earlier cards, but just

these are the cards.

I’m left with.

Number of sub-problems is– hmm?

n.

How many choices of i

are there? n choices.

This really important.

It’s really useful that we’re

thinking about suffixes.

It’s not that some subset of

the cards have been played.

That would be really hard,

because there’s exponentially

many different subsets

that could be left.

It’s always a prefix

that gets played,

and therefore suffix is left.

And there’s only n

suffixes, remember that.

We’re going to use it over and

over in dynamic programming.

So now we need to

solve the sub-problem.

Starting from ci, what’s

the best way to play?

Well, the first four

cards are fixed,

and then we guess how

many hits are left.

So it’s going to be

something like n minus i

minus four different

possibilities for– I mean,

that would be the

maximum number of hits

I could take all

the remaining cards.

That would be the most.

And let’s see, so the number of

choices– I’ll just say it’s,

at most, n.

I don’t have to be fancy here.

OK, now we go to the recurrence.

So I’m going to call

this blackjack of i.

It’s going to be the solution.

I want to solve this

sub-problem from i onwards.

What’s the best play?

And I guess it’s going to be a

max if I’m measuring winnings.

And what’s the winnings if I

decide to hit this many times?

It’s a little bit hard to

write down the exact formula.

I’m going to write a

rough version which

is the outcome of

that first play.

It’s going to be either I

lose $1, we tie, or I win $1.

So if we end up

with the same value,

you actually– in

most versions–

you get your money

back, nothing changes.

The bet is nullified.

So that’s a zero outcome.

But if we’re only

betting $1, these

are the three possible outcomes.

You can compute this, right?

If I told you how

many times you hit,

then you just execute

through those cards

and you compute the

values of my hand,

of your hand versus

the dealer’s hand.

You see, did anyone bust?

If so, they lose.

Otherwise you compare

the values and you

see which is bigger or smaller.

This is easy to

do in linear time.

No biggie.

What’s useful here is

that the dealer strategy

is deterministic.

So after you know how many cards

you take, what the dealer does

is force, because he just looks.

Do I have 17 or greater?

If not, take another card

and keep repeating that.

So it’s a

deterministic strategy.

In linear time, you can figure

out what the outcome is.

Then you also have to add the

outcome of all the remaining

cards, which is just BG of j.

This is recursion, super easy.

We do this for all choices of j.

It’s like a range of i

plus 4 up to n, I think.

Sure, that’ll work.

I should probably

put an if here,

which is if it’s a valid play.

There are some constraints here.

If I’ve already busted,

I can’t hit again.

So in fact what you have

to do in this for loop

is say, well, maybe

I take another hit.

Maybe I take another hit.

At some point I go

over 21, and then you

have to stop the for loop.

So I’m writing that as an if.

You can also do it with a

break, however you want.

But that’s– you’re considering

all possible options,

all valid options of play.

For each of them, you

see what the outcome

was after the dealer

takes some more cards.

This is actually a

little bit funny.

Sorry, this should really be

the number of hits in range

from, let’s say, 0 to n.

Maybe you don’t hit at all.

And then j is a

little bit tricky,

because this is actually i

plus 4 plus the number of hits

plus the number of dealer hits.

OK, so you have to

run this algorithm

to compute what

happened, which computes

how many times a

dealer took a card.

That’s how many

cards got consumed.

And so that’s– if you do i

plus 4 plus that plus that,

that’s how many cards are left,

or where the cards resume.

And then you call BG on that.

So we’re, in general,

from BG of i–

if you think of the DAG–

there’s some position,

maybe i plus 4 happens.

Maybe it doesn’t happen.

It depends on what

the dealer does.

We’re going to depend on

i plus 6, i plus 5 maybe.

It’s going to be all

of these possibilities.

These are all different plays.

And then on each of

these edges, we’re

going to have plus

1, 0, or minus 1.

Those are the outcomes,

whether I won or lost or tied.

And then we’re just computing

a shortest path in this DAG.

It’s actually really easy if

you think about it that way.

This is just how

many cards are left.

From that position, you just see

what are all the possibilities?

What are all the edges

that I could go to?

What states could

I to go to next?

How many cards are remaining?

How much did it

cost me or win me?

And then take longest

paths in that DAG.

That will give you

the exact same answer.

That’s what this dynamic

programming is doing.

In the lecture notes, there’s

more details where I actually

tried to write out this

function, this recurrence

as an algorithm.

You could do it, assuming

I’ve got everything right.

It’s not that hard.

The order here is just the same

as the order we did before.

The running time is going to

be cubic in the worst case,

because we have– it’s

a little non-obvious,

but we have n sub-problems.

For each of them,

we have n choices.

And for each choice we have

to run the dealer strategy.

And so that conceivably

could take linear time.

Here I’m assuming a

general value of 21.

If 21 is actually

constant, it only

be constant time to

play out a single hand,

and then it’s quadratic time.

So it depends on your model

of generalized blackjack.

But that’s it.

And get some flavor of the

power of dynamic programming,

we’re going to see it’s

even more powerful than this

in the next two lectures.

So is the optimal solution of a DP the longest or shortest path of a topological sorted DAG? I know Dr. Demaine states shortest at the beginning, but at the end it seems that he meant longest path for the black-jack example? Perhaps it matters if you guess is searching for the MIN or MAX of a series of choices, which i think would be fine since I believe finding the the longest or shortest path is linear time for topo. sorted DAGs.

Nice lecture! But still did not understand shortest path 🙁

I dont understand this! 🙁

Best one…lecture filled me with lot of energy

Black-haired girl was on time this class.

Did the camera person change or something? I got headache after a while, not because of Erik or the content, but heavy camera movement!

Well shouldnt the j vary from i+1 – n in the text justification problem ?

Super exciting~~~ I like this~ haha

anyone have idea why does in degree(v)+1 come from, to be exact, the "+1" come from?, I have thought about it quite for some time, still unable to figure it out.

this professor is awesome

He was a child prodigy !! Genius is the word !!

https://www.youtube.com/watch?v=qd5oc9hLrXg rules of blackjack

In text justification problem, shouldn't the number of ways to arrange n words be 2^(n-1) ?

For blackjack, if you use suffix don't you start from the end where i is from # to 0? Say for example for 52 cards (standard) what happens if and when the algorithm decides that the first hand starts at card 2 but you need 4 cards to deal with? Doesn't that mean that hand is scrapped since you only have 2 cards to start a hand?. And when you actually follow the output of the algorithm the first hand will actually use 4 cards instead of 2 and the output is meaningless since the first hand has started with 4 cards in reality instead of 2 (meaning everything shifted over by 2 cards and you can't use the output anymore) that the algorithm thought would be discarded? Isn't this the reverse?

Having this guy as the lecturer in the course I'm taking (Algorithms, design and efficiency) would make the course so much more interesting and easier to follow. Thank you & MIT for these educational videos!

Aaaand thanks to this I may have an actual chance of passing through tomorrow's exam.

Thank you

Now, time for some Team Fortress 2 :v

I was so demotivated about studying and my exam is tomorrow!

Erik excitement motivates me somehow. He's really passionate! 🙂

Could someone help me understand why the number of subproblems is n for both text justification and blackjack?

"But that's what dynamic programming is for — you don't have to think." (21:58)

I didn't understand the "suffixes", at 25:00. what is that for?

I would love to see an implementation of the "Text Justification" algorithm

King

25:55 ; How is the time complexity 2^n, if we try to fit in every word into the a single line, then abort and repeat?

Text justification starts at 17:06

Blackjack starts at 38:51

Its a Portal t-shirt.. man i love that game 😀

I thought everyone at MIT knew how to play blackjack… 😛

Will I ever learn dynamic programming? probably i am just dumb and this is not my cup of tea,

Can someone pls explain to me why, in the Shortest Path example, total time is written as O(VE) when #subproblems = O(V^2) and time per subproblem = indegree of the vertex.

I am thinking it should be O(E.V^2). Can somebody pls explain ?

That Portal t-shirt !

I love Erik Demaine. He is unbelievable. All great lectures! Thanks Erik.

could any one guide me which book to use for this topic cause cormen is actually not taking up these algos

@Mit Opencourseware, is the homework, labs and other handouts available for this lecture

Pretty poor demonstration of the BlackJack game. Eric took a dealer hit on 17 which is not allowed. Victor incorrectly stood on soft 18 against a 9 and 10. An intuitive explanation of why the dealer has an advantage is that he gets to go last i.e. if both player and dealer bust the player busts first and loses. The cheating method of a perfect information deck was accomplished in the 1970s by a cheat swapping in his own pre-arranged shoe for the dealers. This resulted in the card shoes being chained to the BlackJack table. On the upside Eric has great handwriting. fun lecture overall.

Prober Proof

Erik Demaine is clearly brilliant. I believe occasionally his teaching to commoners could be improved with more time spent in advance so that he doesn't correct his algorithms midway through, but I is plausible that, for the good of humanity, his time may be better spent on his research.

I'm watching this video at 2x speed and it just looks like Erik had waaaay too much coffee before coming to the lecture.

lol, super nerds front-row

Name of the red book on the table at 41:55 please? Is it Skiena's Algorithm Design manual?

Somewhere in India, I mention to my mom, do you know who this guy is? He's a prodigy, now he teaches at MIT and I can't wait to watch each of his lectures, here on my laptop.

Thank you MIT, Eric, the Internet and Computer Science in general for existing and making all of this possible.

"I didn't realize that all problems can be expressed as DAGs" – You can describe all finite state machines as DAGs, no?

What is DAG?

Where’s all the Indians saying MIT was so easy??

49:15 That's what

hesaid.Did he explain what he means by badness? Is it just me where I feel he just brushed very vaguely on these subjects? Is that the intent?

This is so far over my head wow lol

any 50.004 students?

List of remaining items is called "tail". It's a thing in functional programming.

Based on the lecture above, created an easy to understand animation for text justification https://javadatastructuresandalgorithms.wordpress.com/2018/12/27/text-justification-algorithm-animation/

Great explanation

Why word's strategy is not better

I wonder how you'd handle the value of Ace in the blackjack algorithm

I don't understand the text justification problem. Someone pls helps me.

26:22 … No this is what makes dynamic programming .. well, dynamic programming!

The "latest" Word as of 2013 does not have smart line justification. Now it's 2019 Word still does not have it. From time to time I have to delete/change a word to make the next line not too ugly…

40:28 that Hoodie Shirt meaning MIT 🙂 for who curious

for the text justification, i cant see where the memoization happens. To me, DP(i) is a recurrence function that elaborates the subproblems and min(dp for j in range(…)] is just gonna calculate all the possible new lines. I guess we are to maintain a memo table in the course of bottom up actions which are automated at the end of recurrence? is the job of the memo table to record the dp of i onwards that might have repeated in the course of elaboration？

For an academic video, there are a lot of n-words.

Yeah unfortunately this was really confusing. No code examples, no clarity, just random babble that left me utterly confused.

Do MIT students ever ask questions?

I have a hard time finding how "page width" is actually computed in badness(i, j).

Professor: " This talk will be about DPs and BJ with some text justification."

Interviewer: "What about BJs?"

Professor: "About BJ, (as I said at 49:15) if I've already busted, I can't hit again"

Interviewer: "But what is the general starting point?"

Professor: "Well the base case for a 2×3^2 problem is 18 but as I said at 49:18 : maybe I take another hit , maybe I take another hit again, maybe I take another hit again. At some point I go over 21 and then you have got to stop the for loop."

Interviewer: "What exactly are we talking about? Weed? Young women?"

Professor: "Absolutely not. THIS IS COMPUTER SCIENCE! (/SPARTA) =D"