DP 6. House Robber 2 | 1D DP | DP on Subsequences
ฝัง
- เผยแพร่เมื่อ 11 ก.ย. 2024
- Lecture Notes/C++/Java Codes: takeuforward.o...
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/take...
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.o...
You can also get in touch with me at my social handles: linktr.ee/take...
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
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.
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 :) After listening to logic without further viewing code, I am abe to code the logic on own!! Nice series bro 🔥.... Tons of love 🥰
understooddddd , Woww this man has so much knowledge , he deserves the google job and more , Keep going bro , you have a long way to go , all the best for tuf+
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.
Understood 🔥🔥✨
A great playlist, great explanations and a great teacher !!!!
What else anyone need ?
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
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);
}
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.
Production quality code wow this is what even interviewers expect ,thnks for such a good quality of code as well 💯🔥
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
Makes video at late night for free. Striver is the definition of an educator🗿.
Tons of love brother, your dedication is what makes you different from others!
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
Thanks a ton for making such educative videos and also for taking the time to correct the mistakes(if any) in the video!
understood bhaiya❤...whenever your heart is broken. don't ever forget that you are golden......enjoy....1000 !!
understood and imprinted in memory forever
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
Amazing Playlist Striver
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.
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);
}
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
/*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.....Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
Loved the content, the neighbour logic followed reduction to existing problem which was simply amazzziiiing ❤🔥❤🔥❤🔥❤🔥
Understood😍First channel makes me understand about algorithms such as recursion, backtracking and dp.
You have made topics like dp easier to understand. Hats off man.
Understood , thanx bro you explained the problem as simple as possible
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
Striver your videos are really helpful. Thankyou so much for such valuable and top-notch content❤
Understood , Its a great logic the way you explain it makes it super easy💯
Understood man!!!!
Thanks a lot !!
Amazing video.
Just a comment regarding the extra space. We could have passed the original array instead of making two separate ones along with start and end indexes! Cheers!
interseting to see how simply you broke down the logic
7/57 done!!! Understood!
Sir, we can make two functions by running loop from 0 to n-1 and in another function from 1 to n and call these functions to get answer . I think by this way we don't have to take extra arrays.... Thank you ❤
what a logic .......thanku striver ......understood
Understood Striver Thankyou for this wonderful lecture
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.
understood, thanks for this amazing series...
with each day ,i am becoming master in dsa bcoz of u,
better understood
Clear and Best Explanation!!!❤❤
Understood completely !!❤❤❤❤
Understood. Thanks a lot bhaiya for such a great playlist.
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
// Variables to keep track of the maximum amount of money at each step
int prev1 = 0; // Maximum amount when excluding the first house
int prev2 = 0; // Maximum amount when excluding the last house
for (int i = 0; i < n - 1; i++) {
int temp = prev1;
prev1 = Math.max(prev2 + nums[i], prev1);
prev2 = Math.max(temp, prev2);
}
int max1 = prev1;
prev1 = 0;
prev2 = 0;
for (int i = 1; i < n; i++) {
int temp = prev1;
prev1 = Math.max(prev2 + nums[i], prev1);
prev2 = Math.max(temp, prev2);
}
int max2 = prev1;
return Math.max(max1, max2);
}
} @takeUforward have look on this solution
Dada the way you teach...it actually feels ki yes I am learning the concepts well...thnx a lot for this series
Understood , Thanks Striver
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
Striver, "Understood!"💖💖💖💖
UNDERSTOOD
at a time 2:53 you are making video, this gives us more strength to learn & watch more videos of yours❤❤
Nothing is better than striver .
Highly motivated sir...if you can make efforts to record the video at 2am the least i could for myself is watch and learn...us.
Understood ❤
US :) Appreciate your efforts
PS:- Commenting today when I have no job.. Will come back and comment again when I will get a new job. Till then, Thanks in advance Striver
THANK YOU STRIVERRRRR!!!!!!!!!!1
UNDERSTOODDD!!!!!
Understood...Completed 6/56
Understood very well
if we ignore the last element then it means from 0 to 2nd last element maximum sum.It doesnt mean that you are taking one for sure, your subsequence might not contain first element in this case we can add the last element as well .....isnt it??
I regret why I cant follow you earlier. Thanks a lot.
Understood Striver🙌
understood ❤ You are amazing man , love u so muchh 😍
Python solution of prob mentioned in this video
def max_theft(a):
n = len(a)
prev1 = a[0]
prev2 = 0
for i in range(1, n):
pick = a[i]
if(i>1):
pick+= prev2
not_pick = 0 + prev1
curr = max(pick, not_pick)
prev2 = prev1
prev1 = curr
return prev1
a = [2,3,2]
if(len(a)==1):
print(a[0])
print(max(max_theft(a[1:]), max_theft(a[:-2])))
wonderful series bro, i loved this keep doing good work, these things come back
Another similar way: We can choose to take A[0] or not in solution: ```return max(helper(arr, 1, n), helper(arr, 2, n-1) + A[0]);```
Understood 😄
Understood
Is this logic right even for negative integers?
Superb Content!!!
"understood" bhaiya i had a question like we are taking extra array for storing temp and temp1 so waha to space ja raha hai
understood
clearly undershood ..i appreciate for your work sir;
Understood! made especially easy after watching the last video!
Pure genius
NICE SUPER EXCELLENT MOTIVATED
okayyyy this was amazing!!! day1 and 6 videos done!!!
great explanation
Understood Awesome explanations!!
A request to add Interleaving Strings and Catalan number problems
I am proud to have You 🥰 in my Life.
Understood and awesome as usual
"UNDERSTOOD!!"
Understood !!!!
Understood Understood Understood!!! Best Sir ever🥰🥰🥰
Understood very easily😊😊
US bhaiya, awesome intuition!
Understood. salute to ur hardword. Inspiring.
Thank You
Thanks for great explanation.
UNDERSTOODD!!!
Day 2
guys can use indices instead taking extra 2 arrays
Wouldn't the first and last indices be included if the values are something like {10, 2, 3, 4, 20}? I might be missing something out here, but the same code for DP 5 (without any logical changes) worked for this problem for me.