## Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition

all right so what we're going to look at

in this video is another dynamic

programming problem it is called egg

drop and this is another pretty

I wouldn't say famous but well-known

dynamic programming problem and just to

get this out of the way yeah I know this

was the same sweater I had in the last

video I'm in the same basement and yeah

alright so this problem asks us given a

certain amount of floors and given a

certain amount of eggs what is the least

amount of egg drops the least amount of

egg drops that I need to perform to find

the pivotal floor we're right below it

if I drop the egg it won't break and

right above it if I drop the egg it will

break we're looking for that pivotal

floor so for example if I'm at 3 if I

drop it it doesn't break but as soon as

I hop up to 4 if I drop it and it breaks

I know my pivotal floor is 3 that is the

floor where if I go up even one higher

my egg is gonna break if I drop it and

so the key is we have a limited amount

of eggs and we want to minimize the

amount of eggs we use that is the whole

point of this problem so our job is not

actually to find that floor art our job

is to tell me tell the caller if I give

you a certain amount of floors and I

give you a certain amount of eggs tell

me the least amount of eggs that you

will need to drop to find the pivotal

floor I as a caller I don't care about

the floor I care about you telling me

what is the least amount of eggs that

you are going to drop in the worst case

to ensure ensure that what you tell me

is true so if you tell me that the least

amount of your eggs you'll ever have to

drop to find the pivotal floor is - I

have to be guaranteed of that so as a

programmer what I want to do is I want

to find the worst amount of eggs that I

will have to drop to find a floor

because that guarantees that that amount

is the worst amount we'd have to drop

and that guarantees that I'm going to

find the floor because I'm accounting

for that worst case if that makes sense

so let's do a walk-through Elmi core

sense this is a very difficult problem

to grasp at first so what we're going to

do is we're going to walk through these

simulations and we're going to define

base cases so let's define our first

base case so imagine we have one egg

what we're going to do is we're going to

see if you give me six floors and one

egg what is the least amount of eggs

that you're going to have to drop to

find that pivotal floor so if I have one

egg what is my strategy going to be

well I can't start at floor six I can't

drop from floor six what if my egg

breaks if my egg breaks when I drop from

floor six then I'm going to have zero

eggs if you drop an egg and it breaks

you don't have that egg you lose that

egg and you no longer have any eggs to

do testing on the rest of the floors so

if I drop my one egg from floor six

that's a bad thing to do because if it

breaks I don't know which of these

floors are the pivotal floor

so my strategy instead is going to be

I'm going to drop from floor zero and

instead my strategy is going to be I'll

drop one egg from floor one if it breaks

then I know that my pivotal floor is one

below me I'm going to drop from floor

two if my egg breaks then I know that

the pivotal floor is floor one if it

doesn't breaker one or two I'll drop it

from three I still have the egg because

it didn't break if I drop it from floor

three and it doesn't break I go to floor

four and then five and then if it breaks

a five I know that the pivotal floor is

floor four so in the worst case our

floor where our egg is going to break is

at the very top floor so what we're

going to do is we're going to break this

sub problem down like this so

you give me one egg and you give me any

amount of floors I don't care if you

give me zero floors or give me a

thousand floors

my strategy is going to be I start from

floor 0 or 1 whatever you choose is like

a base and then we're going to go

upwards we're gonna try every every

floor going up until our egg breaks so

what is the worst because remember my

caller wants a guarantee I need to

guarantee my caller that the amount I'm

returning them is the least amount of

drops I can do to guarantee I find that

pivotal floor so what we care about as a

programmer is we care about finding the

worst amount of drops that I have to do

is going to guarantee my caller I'm

going to guarantee them that this is the

worst I'd ever do and that means this is

an upper bound on the amount of eggs I

will ever drop and therefore this is the

least amount to guarantee to you caller

that this is the amount of eggs that I'm

going to have to drop at least to

guarantee to you that I have an ability

to find that floor you want if I have

one egg the upper bound is going to be

the amount of floors I'm given at worst

this egg breaks up here and I will have

to do this many drops I'll have to drop

it one drop it 2 3 4 5 6 drop at all the

floors and that's the worst case so what

is this equal and this is base case

number one when we have one egg I don't

care what floors you give me give me any

amount of floors my upper bound on the

work I'm going to do is going to be the

amount of floors

that's the worst amount of drops I will

have to do to guarantee to my caller

that I'm going to give them a guarantee

of me finding that pivotal position so

this is base case number one we have one

other base case so let's look at that

right now okay so now let's investigate

base case number two our first base case

related to the amount of eggs we have

now our base case relies on the amount

of floors we have and

and our caller does this okay my caller

says here you go

here's a hundred eggs and here is one

floor what is the minimum amount of

drops you can do to guarantee to me that

you're going to give me the pivotal

floor so if I just have one floor you

could give me a million eggs it does not

matter the amount of drops I'm going to

have to do in the worst case is one drop

I just drop it from floor one if it

breaks that means that is the pivotal

floor I can't fix that means that is a

floor where the egg breaks the pivotal

floor would be technically floor zero if

that's even a true floor so the

equivalents for this is no matter how

many eggs I get if I have just one floor

the amount of drops I have to do is

going to be one it's going to be the

same amount as the floors I get so give

me any amount of eggs if I have one

floor the answer is going to be one drop

at worst to give my caller that pivotal

floor I only need to drop one egg that's

all I have to do my worst case is I drop

one I have an answer so this is what we

give our caller our caller wants this as

the answer so what if our caller asks us

this our caller gives us 10,000 eggs we

have zero floors to drop from this is

technically base case three or if you

merge these two base cases we just

looked at base case two if I have 10,000

eggs give me all the eggs you want if I

have no floors to work with what is the

worst amount of drops that I have to do

to guarantee my caller I can find the

pivotal floor well that's going to be 0

drops we can't do any drops so it's

going to be the number of floors we got

0 so I can return to my caller 0 and

remember this maps to this we get 10,000

eggs 0 floors the worst amount of drops

I do to guarantee my caller is going to

be 0 drops

so let me reexpress the base cases to

you in code pseudocode so this can

really drill in before we continue

with our understandings okay so the

reason I'm taking is so slow is I really

want you to understand the base cases it

all starts with our fundamental

understandings of the base cases so this

is why I really want to drill this in so

again here's what we just reviewed or

here's what we just talked about so here

are the floors

if I get one floor or zero floors I

don't care about whatever amount of eggs

I get what I return is the amount of

floors if I have one floor I'm gonna do

only one trial at worst if I have zero

floors I'm gonna do zero trials at worst

so the eggs if I have a total amount of

eggs of one no matter what I do I am

going to play it conservative I'm going

to go from zero one two three four five

six and I'm going to be conservative

going from bottom to top and I'll keep

dropping the egg because remember if I

drop the egg and it breaks game over I

have no more eggs to work with and I

can't guarantee my caller that I can

find that pivotal floor so we return the

total amount of floors because of this

conservative linear strategy we follow

so these are the base cases and now that

we fully understand what we're

converging to now we can see how we

perform that reduction of subproblems

how we split things down into

subproblems so let's look at another

example with two or three eggs so what I

always want you to think about is think

about your base cases first

after you think about the base cases

think about how these subproblems reduce

think of subproblem decomposition after

you do that you can decompose towards

your base cases so let's see an example

of this and how we do that for this

problem by using three eggs and we're

going to have six floors so this is what

the caller asks of us okay so you see

how our caller wanted the amount of

minimum drops to find the pivotal floor

for three eggs and six floors so our

job is to run a simulation our job is to

act as if I dropped from floor 1 I

dropped from floor two I dropped from 3

4 5 6 I'm going to act as if I'm going

to drop from each of these floors and

start my approach from each of these

floors we're just simulating what would

happen because we want to find the worst

case we want to find the situation we

put ourselves in that gives us the worst

outcome because that worst outcome

amount of drops is going to be the worst

amount of drops we do to guarantee we

find the pivotal floor which is what our

caller wants so what we're going to do

is we're going to break this down into a

sub problem we're going to look to

answer this sub problem I need to know

the answers to all of these sub problems

so I can see which one is the worst and

then once I know the worst one what I'm

going to do is I'm going to have that as

the answer for this sub problem ok so I

need you to stay with me here because

this is where it starts to get confusing

so if I drop from each of these floors

again we're still working with this sub

problem I have three eggs in my hand and

I have 6 floors to work with I'm going

to pretend that I start from each

different floor with each amount of eggs

what were the two possibilities that I

need to express what were the two

possibilities that can happen I drop an

egg and it breaks or I drop an egg and

it does not break so what does each of

these entail again this is going to

allow us to express the answer to each

of these in terms of more subproblems so

this is what it looks like so I don't

want to fill these out yet but I just

want you to see our sub problem starts

here what we do is we want to do a worst

case simulation and what we do is we try

a very floor with the amount of eggs and

what happens is we do more decomposition

so if I have six floors and three eggs

there are two ways that these can go and

do you see how more subproblems happen

the reason this is dynamic programming

because we're going to need to cash

solutions we might repeat work so that's

a later concern that isn't going to

concern us right now but we know we're

going to be doing more subproblems and

so now this is another mental leap I

need you to make this is a hard problem

and this might not all click it once but

we're going to see how these subproblems

fork so okay I have six floors and three

eggs if I drop an egg what can happen

the egg can break or the egg cannot

break so what's going to happen is my

total eggs will either stay the same

notice how I just put a three for the no

break for the no break that means that

my egg did not break so what I'm gonna

do is I'm going to put a three-fer are

called we're going to keep the amount of

eggs the same none of the eggs broke but

which way do I go

imagine I drop a floor three my egg does

not break where do I go I go upwards

right I'm going to try the floors above

me so what does the sub-problem

decomposed into so what we see here is

we have six floors and three eggs if I

drop at the sixth floor my egg does not

break I have three eggs and if I have

three eggs and now what I'm gonna do is

I'm gonna go upwards well there's

nowhere to go upwards but here is what

we're going to do we subtract six

the total floors from the amount of

floors we just simulated 6 minus 6 is

zero so if I go upwards I have 0 floors

to work with this looks familiar that's

a base case so we'll materialize that

later so I put this down here again the

total floors of the subproblem we're

working on - the simulation floor which

is 6 6 minus 6 is 0 so let's go down

here the simulation of 5 floors and 3

eggs i drop an egg it does not break

where do I go I go upwards because I

need to invest

further and what's gonna happen is five

is the current floor

the total floors is six floors 6 minus 5

is 1 so do you see that do you see how

we're sub problem you down because if I

try the fifth floor and I don't break

how many floors do I have left to work

with if I go up all I have is one floor

so does that make sense that's why we do

that there and again this is a difficult

problem you don't have to absorb all of

this right now but just follow me

through the sub problem and eventually

will understand this together and then

we have four floors to work with so our

n is dropped it does not break so then

what we do is 6 minus 4 is 2 if I drop

from 4 and I need to go up because more

investigation needs to happen up I do

6 minus 4 to 1 to 2 floors are above 4

so we put 2 there okay so we have three

floors and 3 eggs my egg does not break

6 minus 3 3 if I go up I have 1 2 3

floors so let's put that and then the

same thing for 2 we're just finishing

off if we do not break 6 minus 2 is 4

and then if we're at floor 1 I drop an

egg it does not break I go upwards and

then I'll have 1 2 3 4 5 floors to work

with 6 minus 1 is 5 so this becomes 5 ok

great so we finished our no breaks and

now we understand why we branched that

way because we're doing simulations of

the worst case sub problems and remember

we're converging to the base case we're

breaking this down so we get to our base

cases I don't know the answer to this I

don't know the answer to these I know

the answer to my base cases though and

as long as I converge to them then I'm

going to get the answer I want so what

we're going to do now is investigate if

we break so if we break what happens so

if I have 6 floors and 3 eggs I drop it

for them from floor 6 how many eggs do I

have left I have 2 eggs and then let's

fill it out for all these other

subproblems that branch towards the

break ok so now we see that this is 2

and if I drop an egg and it breaks I

lose an egg and which way do I go I

don't go upwards cuz my egg is gonna

keep breaking if I drop upward I move

one floor down if my egg breaks a floor

four I try floor three so what I'm gonna

do is try floor three so if I have six

floors my egg breaks I'm gonna go down

to floor five if I have five floors and

three eggs and my eggs breaks I'm going

to go down to floor four if I have four

floors I'm gonna go down to floor three

if I have three floors I'm going to go

down to floor two if I have two floors I

go down to floor one and if I have one

floor I go down to floor zero and I want

you to notice that what we're doing here

is we're sub-problem account and notice

that these are base cases we know the

answer to zero floors we know the answer

to zero floors we know the answer to one

floor and this is going to keep breaking

down until we get to our ultimate answer

okay so we have our dynamic programming

table each of these cells mean something

specific that cell right there is our

original sub-problem if I have 3x + 4

floors what is the answer that cell

right there says if I one egg and four

floors what is my answer if I have zero

eggs and one floor what is the answer so

what we want is right there that is the

original sub-problem and what we're

gonna do is we're gonna build up to that

sub-problem and again the code is in the

description if I haven't said that you

can look at the code I have a huge

example a ton of comments there so this

can be really clear for you if you check

the code out watch this

which ever helps you learn better so

what we can do here is define our base

cases so this is kind of not something I

mentioned but if we have no eggs then I

can't do any drops so no matter what

floors you give me I'll just have 0 as

the answer okay and if I have 0 floors

how many drops can I do to guarantee an

answer well it's going to be 0 remember

we won't have to do any drops if I'm not

given any floors if I have just one

floor it does not matter how

many eggs you give me I'm going to be

doing one drop that was our first base

case so let's define that now okay so if

I have one egg how many drops am I going

to have to do remember we upper bound to

the worst amount which is the amount of

floors were given so this is what this

looks like so you could do that with

four loops you can do it in any order

you want as long as you have those

properties and again the link is in the

description for the code so what we're

going to do is we're going to start

right here we're going to try to solve

this sub-problem so what is the answer

to this sub-problem okay so we want the

answer to that sub problem right there

and remember what I said

simulations we want to simulate so we

know the worst case at the cell so I'll

simulate dropping from one floor with

two eggs and I'll simulate dropping from

two floors with two eggs so we'll do

this okay it is a competition who is the

winner who is going to do the worst I

need to upper bound the worst I do it

the sub problem so I can guarantee my

caller that I'm going to find the

pivotal floor so in order to resolve the

competition I need to do a simulation at

the floor and there's two possibilities

the egg breaks or it does not break so

if it breaks then we lose an egg and we

go downwards if it does not break then

we're going to keep an egg and we're

going to go upwards so let's do each of

those simulations okay so here's the

simulation if it does not break I keep

the same amount of eggs does not break I

keep the same amount of eggs but I go

upwards because I want to investigate

upwards I do

the amount of floors that I'm testing

for this cell minus the floor that I'm

simulating on so two minus the

simulation floor one so two minus the

simulation floor of two so what does

that materialize into it turns into that

so what we have here as well is if it

does break we go downwards by one floor

so one minus one the Sydney

lesion floor - one simulation floor -

one and what do they become alright so

my camera died so I'm just gonna finish

the video here so our original sub

problem was right there and what we did

was we made a simulation we made a

simulation right oh my god right there

right here and what we do is we already

know the answer to those two sub

problems so they materialize and what we

want to do is we want the answer to this

sub problem is going to be one plus the

worst of our simulations right so when

we take the worst of our simulations why

do we add one the addition of the 1 is

to signify the fact that we're going to

be dropping from this sub problem so

what we did was all those simulations we

did were different floors we could have

dropped from and this is because we're

trying to bounce the worst amount of

drops right so we did all those

simulations and we want the worst of

those simulations so what we do is we

add one to the worst simulation and

therefore that's going to simulate the

actual drop happening so when we

simulate the actual drop happening we're

going to take the worst guy and we add

one to him to simulate the actual drop

and the answer to our sub problem

becomes 1 + the worst outcome so that is

why we add 1 this this will become more

clear if you look at the code I put a

lot of comments and description there

but let's get back to Ben with the time

and space for this all right so for the

time and space complexity we're going to

have an upper bounding of total floors

times total X sub problems how long does

it take to compute each sub problem an

upper bound of total floors we're going

to be performing some fractional work of

total floors at every single subproblem

so that is the upper bound on the work

we can perform at each sub-problem

so what happens is we multiply these

together and our overarching upper

bounds on the asymptotic complexity

becomes total floors squared times total

X so this is the time complexity for the

solution presented so the space

complexity

is going to be total floors times total

eggs we're going to hold an upper

bounding of this many subproblems in our

in our cache so again the code is in the

description if you want to see that I

have the top-down and bottom-up

approaches to this problem there are

more optimal solutions but it's unlikely

that you would get to them in a

45-minute interview and I think that's

kind of the point of all of this for me

it's to get the answers or set of

thinking that you would actually ever

use instead of learning the actual

mathematical ways that are kind of a

waste of time to learn because you can't

memorize every problem all right so that

is all for this video if you liked this

video hit the like button and subscribe

to the channel again I want to make this

one of the world's largest resources for

software engineering preparation and

interviews because I think we need a lot

more you know down-to-earth clear

explanations where things are explained

as a student should learn them so that's

kind of my mission and goal with this

channel and with these videos

[Music]