So I bet you've all heard the news, this is super amazing.
We have found an antidote for coronavirus the antidote.
Oh, yeah.
Same old story, huh?
Let's just call it play to win quarantine.
What's this?
So we are faster than hundred percent.
The antidote is going at the regressions.
Hey, guys, this is Andy.
Welcome Delver PDA coding in their vacation Monday.
Let's get it started.
First of all, all jokes aside, this period is going to be a little bit tougher because this is something
that I won't say that humanity heaven hasn't seen it before or something like that, but we at least
the younger generation haven't.
So let's just call it play to win quarantine house rubber.
Here we go.
You are a professional rubber planning to rub houses along the street.
Each house has a certain amount of money stashed.
The only constraints stopping you from robbing each of them is that a decent houses have security system
connected and we deal.
It will automatically call and it will automatically contact the police if 30000 houses were broken
into on the same night.
Given the list of non-negative integers representing the amount of money of each house determine the
maximum amount of money you can rub tonight without alerting the police.
This is getting serious.
And when problems like this get serious, I'm going to need my drawing tablet.
I'll be back.
Done.
It's time for Picasso on its work.
And here it is, guys.
Just take a look at this.
I think it's simple.
Perfection for houses, different colors.
Look at that structure.
Look at that drawing skills.
I should be an architect, not a software engineer.
But yeah, after the virus goes away.
So four houses, each of them has a number.
A sum of money, right.
One, two, three and one.
You are the robber, so you can't rob two idea and houses.
And what are our choices here?
Well, I could go and rob the first house, but if I run the first house, I can't rob the second one.
So then I have to choose.
Should I rob first.
And the first house is.
Or the first and the fourth house maybe.
Or I could live the first concert as it is.
I could start robbing the second house.
And after doing this, I can either move to the fourth one or not rob any of them.
Right.
Because if I rob the second one, then I can drop the first one or the third one.
So basically here I have two choices to make.
I will either rob the first and the four houses or I will rob the second and the four houses.
And what is the greater sum?
Well, one plus three is four minus two this two week muffs.
All right.
Big shout out to our favorite rapper.
Right.
So one plus three, four or two plus one free four is greater than free.
So for this example, the answer is four.
Let's take another example and let's jump into the second example.
Again, same perfection and drawing.
So we have no.
Five houses, right, to seven, nine free and one hour there.
Sum of money.
Now, we have to choose here.
But most free houses.
So let's suppose I chose two houses, right.
If I do this, what are the houses that I can choose?
Well, let's say if I choose this seven, for example.
Now, two and nine are blocked.
So I have to choose free or what?
And I'll obviously choose the free ride because it's greater.
All right.
So I have a possibility is to get that.
But let's say I chose nine.
When I do this.
Can choose it with well.
Seven and three are now locked.
So true or what?
Or maybe both.
Why not both?
So here I can choose free houses and they are going to be two nine.
And what I think this is getting a little better, right, because this sum is No.12.
Do I have any better tracing than this?
Well, not really.
So the answer is going to be twelve.
For this example.
Hopefully you've understood the exemplars and the problem.
So it's time for the real business.
Let's try to solve this problem using dynamic programming.
Yeah, you heard it said dynamic programming.
Let's do this.
All right, guys.
So dynamic programming.
Here are the house is right and we are basically the rubber, which is a guy.
Let's draw the guy right.
We are this rubber.
Now, what we can do in this dynamic approach.
Well, my bullet proof formula is something like this on step number one.
I'm going to decide what are my sub problems initially?
I have all these houses which are N minus one.
Right.
So this is basically like the bigger problem.
This is the full problem, right.
Where I have the houses from house number zero, there's index to house number and minus one.
But the sub problems are going to be houses starting from house number zero and going all the way to
house number I.
Because it's a moment of time.
If I am this little guy, this rubber, I will basically start from the first house and I am going to
know from the start what's my plan and how I will rob the houses.
So at some moment of time, I go, I go, I go.
I will be right in front of house number I.
So step number one is to define our dynamic programming and let's actually try to draw it here because
I have more space.
So first then number one, as we said, the sub problem first I hollis's right.
So I'm going to have something like DEPI of I.
What is the maximum amount of money?
Right.
So Max money.
I can take from the first.
From the first.
Oh, my handwriting is terrible, but.
Does the job.
So, all right.
Perfect V.P. of AI is the maximum sum of money that I can take from the first icehouses.
Now, after I have the dynamic programming defined and going through the recurrence relation.
So this is step number two.
So I'm going through the recurrence relation for DEPI of AI.
All right.
So let's say I am this little guy and now I am right in front of house number I.
Yay!
Now, when I'm in front of this house, I basically have two possible options.
I can either rob it or ignore it and go to the next slide.
What shall I do?
Well, I should analyze both the options and choose the one which gives me the maximum amount of money.
Right.
So let's see what are the options in terms of recurrence relation?
Well, when I tried to compute DEPI of I.
First option is to rob House Number I.
So I enter.
I take all your money and then.
All right.
Those are the money.
And then I ran away to the next house is great.
But in order to be able to rob house.
No, I.
I should know for sure that I didn't rob house number minus one because these two are radiation to each
other and I'm not respecting my plan.
So I rob house number I.
So this means I'm going to take I don't know, let's call it a V, right.
V of I.
Which is the amount of money in house number I.
But I have to make sure that I didn't rob this house.
So.
All the money that I can take in addition to this is only from houses starting at position zero and
ending a position A minus two.
So this is V of I plus DEPI of IE minus two, which is great.
Now, the second scenario is if I ignore this house.
Right.
So I basically have no business here.
That was me.
Now it's not right.
This house remains as it is.
If I don't rob this house, well, how will I get the money from the first I houses?
Obviously from the first I minus one houses.
Right.
So all the money that I've got by now remains the same.
So DEPI of I is going to be equal to DEPI of minus one.
And that's it.
Remember scenario number one.
I rob house number I.
I'll make sure that I didn't rob house number I minus one for this.
I need this dippie scenario number two.
I don't rob house number I.
So my money are from the first I'm minus one houses because I want to maximize the amount of money that
I steal.
Of course I'm going to choose the maximum.
Between these two options, and that is basically my recurrence relation.
Step number three, I choose the order in which I will compute these peace.
And the order here is obvious because when I compute DEPI of I am going to use DEPI of IE minus one.
And DEPI of minus two, right?
So these two are states we have the eye less than my current eye.
So what are basically do is that I will compute this DEPI array starting from position zero, going
all the way to position and minus one in increasing order after I do that.
What is going to be my answer?
My answer is always going to be DEPI of M minus one.
So after I have completed going through all the houses and making a choice, I basically have all the
money.
These are the money.
All right, that's good.
And I can go to some beautiful place where it's sunny and I don't know, I'm going to drink some cocktails.
Right.
So this is the problem.
Basic dynamic programming, really nothing special.
But my skills of drawing and explaining things are getting really on point.
So let's go and it God and coded in C++.
First thing we are doing is defining the DPRK, which is a vector of integers, DEPI of sites and.
But who is N.
I need the m n n equals none that size.
If you hear something too special or different, it's my fridge.
Yeah.
So.
Yep.
Make sure you hit the like button.
Make sure you hit the subscribe button.
Make me famous so you won't hear my fridge in the next videos.
So I have money for a studio.
A real one.
But until then, let's have fun, man.
This is the journey.
So DEPI of.
And let's say it's initially zero and.
All right.
Now let's first initialise DEPI of zero because as we have seen in the recurrence relation, DEPI of
AI depends on DPF and minus one NDB of I mean it's two which is quite bad.
Like if I want to compute DEPI of zero, I'm going to use the B of minus one, NBP of minus two.
And I don't really have those positions do I.
So that holds true I guess for DEPI of one two because I can access the of minus one and that's not
cool.
So yeah, let's initialize both of them.
DPF zero means from the first house.
Right.
So what I'll do is I'll take the money.
But the problem is here that let me check if all the numbers are positive, because if they are not.
That's not cool at all.
Like I can lose money if I decide to rob a house.
Right.
So a certain amount of money given non-negative integers.
Perfect.
So the idea of zero is numbers of zero.
Then what is going to be the view of one?
Well, here I have two houses.
So I'll make two choices.
I either Rob first one or second one.
I can run both.
So the big one is going to be the maximum.
Let me type nums here.
Maximum between NOM's of zero and NAMS of one.
That I will start with I from position two all the way to end minus one I plus plus and DEPI of I DEPI
of it should be equal to the maximum between DEPI of minus one.
Right.
And DEPI of minus two plus nums of light.
So those are the two options.
And now everything is good because I can to access elements.
We have negative indices.
And of course as we said, we will return here.
DEPI of N minus one.
Right.
Let's see how I do.
Judging.
Oh, I have accepted on the example that he'd submit.
Fingers crossed.
Come on.
Oh yeah.
Same old story, huh?
I guess the story continues.
Yeah.
I always like I have a tradition.
Always happens to me.
Right.
Every every time, every time I try to solve a little problem.
Every time I get this error.
Well, I guess I have to learn my lesson someday, but not today.
So, yeah, basically what happens here is that our vector could be empty, of course, because.
Why not?
Like, I'm a robber and I go to an empty place where no people live and I want to rob it.
Yeah.
And they'll end up robbing my house instead.
So yeah.
If numbs that empty, this is how we check it.
If a vector is empty.
What should we do is that we basically should return zero and that's all.
So submit again.
Submit again to idle.
Fingers crossed.
Oh.
One other runtime error.
Oh all.
That's a new one.
All right.
I'm getting a bit rusty here.
That's right.
Because what we do here is that.
Oh, yeah.
That's nice.
That's actually pretty nice because I initialize no DEPI of zero in DEPI of one.
There's another error that I didn't expect, and that is if the size of this vector is zero, I got
it handled.
But if it's one, I can't access this element because it doesn't exist.
So what I shall do here is that if this is empty.
All right, return zero.
If nums that size equals one, I should return the first number.
Then.
If the first number is zero and if it's at least two, then everything should be fine.
So now what up?
It should work as a charm.
What's this?
So we are faster than hundred percent of the submissions.
Plus, plus and we use less memory that a hundred percent of the submissions in C++.
That's just amazing.
That is just amazing.
Man base anyway.
If we enjoy this video, make sure you hit the like button.
Make sure to subscribe.
Stay tuned, because we are continuing to play to in quarantine.
Stay safe.