DP 6. House Robber 2 | 1D DP | DP on Subsequences
Vložit
- čas přidán 13. 01. 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/data-structu...
Problem Link: bit.ly/3F6q83P
Pre-req for this Series: • Re 1. Introduction to ...
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we have discussed how to solve the House Robber 2 problem, this is a slight variation of the previous problem that we solved in Lecture 5 of DP series.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
![The moment we stopped understanding AI [AlexNet]](/img/n.gif)
I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.
us
understood
us
understood sir
Bhaiya i always with u.❤
I am watching this in 2024 even now u are the best and no other video like this . Thanks you so much
😮
this is called confidence, even the wrong answer seems accepted!!
just change int to long long int
While reading the question the same approach came to my mind and i was really happy when u explained the same approach
Absolutely the best!! I am able to solve questions on my own too because I am able to think in the right direction now. Thank you Stiver
We can also send indices as f(0,n-2) & f(1,n-1) to the function and compute. Wont need the temp array in that case.
gives TLE
@@abhijitroy1958
class Solution
{
public:
int robOriginal(vector& nums, int start, int end)
{
int last = 0, last_last = 0, res = 0;
for(int i = start; i < end; ++i)
{
res = max(last_last + nums[i], last);
last_last = last;
last = res;
}
return res;
}
int rob(vector& nums)
{
if(nums.empty()) return 0;
if(nums.size() == 1) return nums[0];
int n = nums.size();
return max(robOriginal(nums, 0, n-1), robOriginal(nums, 1 , n));
}
};
That's recursion and not optimised
I have done same thing. Successfully submitted.
You have made topics like dp easier to understand. Hats off man.
I devised the solution without going through the full video and coded and submitted using same logic from L7!! Great teaching Striver!!
Understood 🔥🔥✨
A great playlist, great explanations and a great teacher !!!!
What else anyone need ?
Production quality code wow this is what even interviewers expect ,thnks for such a good quality of code as well 💯🔥
Understood, thank you sir, the logic of leaving the first element and applying maxSumSubseq on the remaining and leaving the last element and considering the starting n-1 element is amazing.
not only did i understand, but i was also able to solve this problem myself, just by watching your previous tutorials. keep up with the good work man
Understood :) After listening to logic without further viewing code, I am abe to code the logic on own!! Nice series bro 🔥.... Tons of love 🥰
Timestamps:
Intro 00:00
Problem Statement 00:38
Intuition 02:22
Coding 06:12
Also, understood
❤
Immense respect for the hardwork and dedication you put into teaching us. the last line you said that you make these dsa videos at night post working hours gave me so much motivation. Youre one of the biggest inspirations striver.
we, your students, are proud of you.
Tons of love brother, your dedication is what makes you different from others!
That click in your brain at 4:55. Like damn striver. You are just too good in teaching
I KNOW RIGHT !!!!!
was like DAMN!
understood bhaiya❤...whenever your heart is broken. don't ever forget that you are golden......enjoy....1000 !!
Understood😍First channel makes me understand about algorithms such as recursion, backtracking and dp.
wonderful series bro, i loved this keep doing good work, these things come back
Makes video at late night for free. Striver is the definition of an educator🗿.
Because of your lucid explanations, i've been able to do this one directly with space optimization in two traversals🙏🙏
you can do it in 1 traversal, using 4 variables
Clear and Best Explanation!!!❤❤
understood bro ,very nice teching bro i liked very much many of them are following your teaching and many suggested about you channel to learn programming thanks bro
In the article it is mentioned that the space required is O(1) but the solution uses O(N) extra space for creating two additional arrays.
Here is the true O(1) space solution
long long int houseRobberUtil(vector& valueInHouse, bool check) //check=true if we pick the first 1st element and false if we don't pick the first element.
{
long long int prev1,prev2;
int i,n;
if(check)
{
prev2=valueInHouse[0];
i=1;
n=valueInHouse.size();
n-=1;
}
else
{
prev2=valueInHouse[1];
i=2;
n=valueInHouse.size();
}
prev1=prev2;
long long int ans=0;
while(i1)
pick+=prev2;
}
else
{
if(i>2)
pick+=prev2;
}
long long int notPick=prev1;
ans=max(pick,notPick);
prev2=prev1;
prev1=ans;
i++;
}
return prev1;
}
long long int houseRobber(vector& valueInHouse)
{
if(valueInHouse.size()==1)
return valueInHouse[0];
long long int inc=houseRobberUtil(valueInHouse,true);
long long int exc=houseRobberUtil(valueInHouse,false);
return max(inc,exc);
}
Question 00:01
Intuition 02:20
Code 06:08
arey khushwaha bhai aap yaha kaise XD
@@parthstark2934 haha
I was able to code the whole ans right after you explained it. Then I watched it thereafter. Thanks Striver.
okayyyy this was amazing!!! day1 and 6 videos done!!!
we can also do it by dp solution of lecture 5 ... just use long long in dp array and make 2 dp array
call the function for (n-2)
reverse the array
again call the function for (n-2)
max of both
@@ojasahirrao3287
according to video
long long int maximumNonAdjacentSum(vector &v1){
long long int n = v1.size();
long long int prev = v1[0];
long long int prev2 = 0;
for(int i=1;i1) take+=prev2;
long long int notTake = prev;
long long int current = max(take,notTake);
prev2 = prev;
prev = current;
}
return prev;
}
long long int houseRobber(vector& nums){
int n = nums.size();
if(n==1) return nums[0];
vector s1,s2;
for(int i=0;i
@@ojasahirrao3287
from DP lecture 5
reversing the array
#include
long long int solve(long long int i,vector &v1,vector &dp){
if(i == 0) return v1[i];
if(i < 0) return 0;
if(dp[i]!=-1) return dp[i];
long long int left = INT_MIN;
long long int right = INT_MIN;
left = solve(i-2,v1,dp)+v1[i];
right = solve(i-1,v1,dp);
return dp[i] = max(left,right);
}
long long int houseRobber(vector& valueInHouse){
long long int n = valueInHouse.size();
vector dp(n,-1),dp1(n,-1);
if(n==1) return valueInHouse[n-1];
long long int ans1 = solve(n-2,valueInHouse,dp);
reverse(valueInHouse.begin(),valueInHouse.end());
long long int ans2 = solve(n-2,valueInHouse,dp1);
return max(ans1,ans2);
}
@@champion5946 Thank you for the code. I solved it using dp(memoisation). I forgot to make two dp arrays.
@@ojasahirrao3287 ✌🏻np
@@leetcoder1159 simp
Understood man!!!!
Thanks a lot !!
UNDERSTOOD.....Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Using *"low"* & *"high"* indices instead of creating new vector
int func(vector &A, int low, int high)
{
int prev2 = 0, prev1 = A[low];
for(int i=low + 1; i 1) pick += prev2;
int notPick = 0 + prev1;
int curr_i = max(pick, notPick);
prev2 = prev1;
prev1 = curr_i;
}
return prev1;
}
int rob(vector& A)
{
int n = A.size();
if(n == 1)
return A[0];
int m1 = func(A, 0, n-2); // Exclude last elem.
int m2 = func(A, 1, n-1); // Exclude first elem.
return max(m1, m2);
}
Problem Link : leetcode.com/problems/house-robber-ii/
class Solution {
public:
int solve(vector nums, int start, int n){
int prev2 = 0, prev = nums[start];
for(int i=start+1 ; i
Thanks for leetcode problem link. Appreciated 🔥
"us" striver sir "us" love ur content and the value it provides
Understood , Its a great logic the way you explain it makes it super easy💯
/*with space optimization (no need vector temp1 and temp2)*/
int robhelp(int start,int end,vector &nums) {
int prev1=nums[start];
int prev2=0,curr;
int fs,ss;
if(end-start==1)
return nums[start];
for(int i=start+1;istart+1)
fs+=prev2;
ss=prev1;
curr=max(fs,ss);
prev2=prev1;
prev1=curr;
}
return curr;
}
int rob(vector& nums) {
int n=nums.size();
if(n==1)
return nums[0];
return max(robhelp(0,n-1,nums),robhelp(1,n,nums)) ;
}
Understood , thanx bro you explained the problem as simple as possible
understood and imprinted in memory forever
what a logic .......thanku striver ......understood
understood, thanks for this amazing series...
Loved the content, the neighbour logic followed reduction to existing problem which was simply amazzziiiing ❤🔥❤🔥❤🔥❤🔥
Understood. Thanks a lot bhaiya for such a great playlist.
Amazing Playlist Striver
Striver your videos are really helpful. Thankyou so much for such valuable and top-notch content❤
Understood , and thanks for making such a great content on YT.
clearly undershood ..i appreciate for your work sir;
Amazing series !!
understood ❤ You are amazing man , love u so muchh 😍
understood. The best dp series
Superb Content!!!
Understood , Thanks Striver
Thanks for great explanation.
Dada the way you teach...it actually feels ki yes I am learning the concepts well...thnx a lot for this series
understood this. thank you sir
7/57 done!!! Understood!
understood and thanks a lot
THANK YOU STRIVERRRRR!!!!!!!!!!1
UNDERSTOODDD!!!!!
Understood very easily😊😊
Understood and awesome as usual
Superbly explained bro, I understood it clear👌👌
great explanation
Thank you so much striver !!!
with each day ,i am becoming master in dsa bcoz of u,
better understood
Thank you very much. You are a genius.
Understood very well
Not used any Extra Space, All 4 codes are below. All thanks to Striver
Brute Force Approach:-
long long int recursive(int ind, vector&a,int end){
if(ind
Understood. Thank you sir
Understood. salute to ur hardword. Inspiring.
Understood Striver Thankyou for this wonderful lecture
Understood !! Awesome Technique
Understood! made especially easy after watching the last video!
Thank you so much :)
Amazing Explanation!!
Good stuff Striver!
Understood sir!!! your way of teaching is so damn amazing😀
I paused the video and thought of this, and I cracked the intuition, also I think there's no need to take two extra vectors, temp1 and temp2, it could be done without that as well. thank you for the video, this is becoming addictive.
We can include start and end indices in function
Func(nums,start,end):
n= nums.size()
---------
For(i= 0,i
understood man!! Thank you so much
Understood amazing !!!
Brilliant, One point we can save more space by not even creating two separate input array instead, Add one parameter in maximumNonAdjacentSum method as starting index and send it as 0 in one call and 1 in another call and play around that.
Amazing❤
thanks striver!
UNDERSTAND VERY WELL SIR
great explanation !!
understood bhaiya
really great content !!
Understood ❤
understood bhaiya this is day 3 and really loving it
Thank U Sir!!
Understood 💯
understood ❤
Understood! Amazing content like always :)
great work man.good content
Understood Awesome explanations!!
A request to add Interleaving Strings and Catalan number problems
Understood! Thank you!
Understood🔥
understood
🔥🔥🔥
Understood 😊
Understood Understood Understood!!! Best Sir ever🥰🥰🥰
understood👍
Understood🎉