DP 19. 0/1 Knapsack | Recursion to Single Array Space Optimised Approach | DP on Subsequences

Подписаться 610 тыс.

Просмотров 245 тыс.

50% 1

Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3KHpP3v
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the problem of 0/1 Knapsack. We start with memoization, then tabulation, then two-row space optimization, then single row optimisation. This problem is the fifth problem on DP on Subsequences Pattern. Please watch DP 17 before watching this.
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

Опубликовано:

15 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 1,1 тыс.

@takeUforward 2 года назад

I need your support, and you can do that by giving me alike, and commenting "understood" if I was able to explain you. The single space thing can be applied to all the subset-sum problems as well. Keeping a like target of 500 ❤✌🏼

@mdmurtaza8321 2 года назад

one of the doubt i am getting how are u converting the base case of memorized code to tablar dp like in this case if(indx==0) { if(wt[0]

@sairishik229 Год назад

can we take the starting value of take as -1 ??

@sayansadhukhan9692 Год назад

@@mdmurtaza8321 The dp is declared as dp[n][W+1]. In this base case we are trying(to handle index = 0 condition, i.e. 0th row on dp matrix) to fill dp[0][0 to maxWeight] so that filling dp for every weight till maxWeight. The for loop is starting with wt[0] because, the base condition is for 0th index i.e. 0th index wt[0] and we have minimum weight at 0th index, the thief can steal whatever element is there on index = 0 until weight of the element is less or equal to maxWeight (wt[0] to maxWeight) .

@stith_pragya 6 месяцев назад

I checked the like count has crossed ever 7000😎

@iamnoob7593 6 месяцев назад

understood

@pragyajha5609 2 года назад

You are one of the most intelligent people I have ever seen. Not finished watching till end, just wanted to tell you. You make me feel I am intelligent too. Thanks @striver.

@udaypratapsingh8923 Год назад

u r right btw : )

@prajjwalgurjar3887 Год назад

@@udaypratapsingh8923 ok bhay

@abhimanyuambastha2595 Месяц назад

Haven see a lot of DP videos, and mostly all of them write the space optimized code including the 1-D array, but not teaches exactly why they wrote it that way. Striver bro great teaching and energy, loved it

@pranjalthapliyal2278 Год назад

Understood :) Can't believe that I was able to solve one of the most famous problems out there on my first atttempt, completely on my own. You may never see this comment Striver, but this playlist is genuinely incredible, so thank you *sooooo* much for putting this incredible content out there, all for free.

@kiransequeira6152 Год назад

space optimization to just 1D array was insane 🤯

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@KinjalDas-ok9hu Год назад

@@MadhavGupta-fi2tu Compare it to the base condition in the recursive solution. We can add wt[0] our knapsack only if its value is less than the target w, so for the index i = 0, we simply looped over all values from wt[0] to the target value w.

@ankurgoswami4441 Год назад

@@MadhavGupta-fi2tu because for i < w[0], dp[0][i] is 0, which is already pre filled at time of vector declaration

@KandulaAsrith 5 месяцев назад

because, suppose that we landed at index=0, with the bag capacity still having >= weight[0], then we can definitely place the item which is at index 0 into the bag. So, for all the values of bag capacity>=weight[0], the value that we can return is value[0].

@aeshwer 2 месяца назад

@@MadhavGupta-fi2tu //Base case - for all wieghts more than maxWeight at zero index will return value else return 0

@paridhijain7062 2 года назад

Understood, I am following this series. I have gone through a few of other playlists but this one is my constant now. Learning each day. You literally mad DP very easy to grasp now. Thank you sir.

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@tanmaybro3812 Год назад

@@MadhavGupta-fi2tu The for loop is starting with wt[0] because, the base condition is for 0th index i.e. 0th index wt[0] and we have minimum weight at 0th index, the thief can steal whatever element is there on index = 0 until weight of the element is less or equal to maxWeight (wt[0] to maxWeight) .

@user-hq6vy2dj7d 10 дней назад

Hey i am learning dev from harkirat wanna ask how to start dsa journey will you please guide me

@ayushsharma7946 2 года назад

The way striver say "WHAT ARE YOU WAITING FOR?" always motivates me more and fills more energy into me..!! Thanks a lot striver.

@anmolmajhi225 2 года назад

Thanks, sir, without seeing this video I can do recursive, recursive with memoization, tabulation and space optimization with two arrays by learning last 18 lectures, and now I can do the one array optimization. This DP series has helped me solve questions easily that I can't previously. Once again Thank you for bringing this amazing DP series. LOVE your work. And Lastly UNDERSTOOD!!❤❤

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@kushalcg3175 10 месяцев назад

@@MadhavGupta-fi2tu Because it is from that index that the item at index 0 can be picked up, before that the maximum weight that we can hold will be lesser than the weight of item 0

@eshandhok2591 Год назад

Mind Blowing Observation for that space optimization, things like these define the difference between a googler and any other person, lot's to learn from you, Striver, in terms of education as well as life lessons. As always, Understood!

@saketaryan2227 Год назад

bruh u just made google sound like iit

@yamanaggarwal6391 2 года назад

I saw so many articles which used just a single array for space optimization and was never able to understand it. Everybody had given vague answers about this and I had literally scouted the entire internet for this explanation. And today I am finally able to understand it. Thank you so much Striver bhaiya. There is no match of you 🙏🙏🙏

@KulvinderSingh-pm7cr Год назад

so True

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@sharan7504 2 года назад

UNDERSTOOD!! that single array space optimization is mind blowing!!...really loved it! THANK YOU SOOO MUCH

@KalingaAbhisek Год назад

At the end of the video space optimisation you told me i was doing the same way in previous questions when i figured it out myself that if we are using previous element of previous array then why dont we traverse backward and compute and store there in that previous array. Now you did it and now i am sure about the optimisation i was thinking. I bet that I Understood............🙂🙏

@shubhankarsharma154 Год назад

Single row optimization was really a god tier stuff... ⚡ Thank you and UNDERSTOOD

@jaiminsolanki5478 2 года назад

Even in the most common problem, Striver teaches something new, thankyou so much Raj Bhaiya!

@nishitar3915 День назад

Every single time you amaze me Raj!!! Hats off to your hardwork man!! Big Salute. And most importantly very grateful to be having taught by you!!!!!!

@vibhanshugarg3603 2 года назад

this is the easiest ever explanation of 0/1 knapsack. Godly insane man!!!

@itsaryanb9316 Год назад

Loved the Single Array space optimised approach !!

@alokkumar-ki7wp Год назад

I never thought I could be able to solve DP problems all by myself, but just a moment ago I did!!!! Thank you striver, You're amazing.

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@brokegod5871 5 дней назад

@@MadhavGupta-fi2tu because you are going from n-1 to 0, so in the last case you have one item left to steal which is basically the 0th item

@zen-g-host Год назад

Hi striver! You are really an amazing person and best mentor we could have asked for, i can't tell you how much gratitude I have for you. Once again Understood!!!

@sonukumarram1880 4 месяца назад

single array technique was mind blowing concept ... thank u striver

@himanshuagrawal8012 2 года назад

Great Series BHAIYA. You are doing a great job. Gradually now I am able to build logic and write the code on my own. #UNDERSTOOD

@parthsalat 2 года назад

Understood kaka The optimisation into a single vector was mind blowing! You clearly deserve Google Warsaw!

@karthikeyan1996_ Год назад

it is already in geeks for geeks if you havent seen this before dude nothing out of the moon

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@rahulmandal4007 Месяц назад

@@karthikeyan1996_ zyada mat bol Adress bata apna pilna h to

@vibhavsharma2724 Месяц назад

Unbelievable that you optimize the code this much. Really you are an extraordinary person. I understood it very clearly. Thank you striver.

@harshitgupta7496 3 месяца назад

Thanks striver! Watched the dp lecture in series. Was able to come up with recursion , tabulation and space optimization into 1D all by myself!

@shineinusa 2 года назад

First of all thank you for the series. I believe the base cases from the previous and this video are un necessarily complicated. You can just check if(idx < 0 || w == 0) { return 0;}, we don't have to make 0 as a special case and write confusing base cases (if else's). once the index 0 is processed like rest of the others indexes, it should stop. I hope you take it as a constructive criticism!☮

@SJ_46 2 года назад

That's right if we only had to do rec and memoization, but in tabulation how will u initialize negastive index?? Ik it can be done, but then memo to tabu step will involve some extra work which is avoided if we do this way, also why will the fn have to handle a negative index in the first place?? it will never occur, idx is always >=0, in yr case it is becoming

@cse048harshkumawat6 Год назад

@@SJ_46 why we didn't write when if(W==0) return 0;

@amansaxena5620 Год назад

@@cse048harshkumawat6 did u find the answer because I am thinking the same?

@vinitkumawat2335 Год назад

@@amansaxena5620 @CSE048 Harsh Kumawat we are only taking particular element if it is less than or equal to W, So even if it becomes 0 in between, then we will keep moving towards base case, i.e. F(idx-1, W) => Eventually it will go in Base condition, and it will be handled there.

@Ani_86_ 2 года назад

The single vector optimization was wonderful 🔥😅

@meetsoni1938 2 года назад

You are travelling a whole journey from recursion-> memorization -> Space Optimisation that is amazing. No one else explain like that 🦾💪💪

@jiteshkhatri2896 Год назад

Aditya Verma also explained in same way and in depth also

@ch0c0_1 Год назад

Tabulation also 🔥

@jeevaalok1467 Год назад

@@jiteshkhatri2896 who's is best at teaching everything briefly in your pov ?

@jiteshkhatri2896 Год назад

@@jeevaalok1467 if u want can share any social media handle where we can discuss.

@naveenramadheni2482 Год назад

@@jeevaalok1467Both are of the same standards, but I chose a striver from Aditya verma becoz I can't understand Hindi.

@yashkhatwani3198 Год назад

Understood , solved all recursive , memoization , tabulation and space optimization by myself .

@omeshdeoli9475 3 месяца назад

was never able to understand how single array space optimisation works excellent explanation striver. Really helpful!!

@balwantyadav724 2 года назад

US sir .. Love the single array optimization....keep going sir.

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@jitendrasinghsola 2 года назад

What a amazing series i am able to do question on my own

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@gauranggupta6422 2 года назад

This is one of the best explanations of this question and the space optimization is just amazing. Thanks striver

@dhruvbajaj5079 Год назад

Great video. First time I am able to understand tabulation and space optimization intuitively.

@souravkumar-eb1wz 2 года назад

Understood Bro. The single array optimization was awesome . It showed the power keen observation 💥💥. Hope one day , I achieve such an observation skill. Thanks for the video bro. Keep the DP series going 💪💪. This is like my personal wish , i would like to see some DP problems based on subarrays in this series , because i find it hard differentiating it from subsequence problems. I believe only you can make me understand. Pls consider this bro.

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@priyankasati8308 2 года назад

Awesome, seriously love the last 1d optimization.

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@ranasauravsingh 2 года назад

UNDERSTOOD.. ! wooooooahhh that last space optimization climax gonna enlighten your brain nerves... Thanks striver for the video... :)

@sangeethagopalan301 Месяц назад

Loved the single array optimisation. U r doing a brilliant job. Thanks a ton!!!

@Saurav_Kumar514 Год назад

1D Array optimisation is really Awesome 🔥❤

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@RupamSasmalYt Год назад

From fearing from "DP" to solve question by my own without watching your solution, it's a great journey! BTW damn good observation to optimize it into single array! grateful ♥

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@shuvo9131 2 года назад

My love for this series getting deeper everyday, thanks for for the last optimization, its amazing

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@RohitKumar-dy2gc 8 месяцев назад

loved your one array optimization technique❤❤

@Raghav1205 2 года назад

Bhaiya one suggestion can you please consider making a video on coin change type problems because it gets confusing when all the permutations are counted and in some only unique ones are counted.

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@codermal 2 года назад

Those who thought of using greedy by sorting according to (val/wt), Test Case: wt-> 3 2 4 bag=5 val->57 36 80 greedy gives=) 80 , while ans=93

@avirupmazumder4840 Год назад

That was fractional knapsack

@codermal Год назад

@@avirupmazumder4840 In fractional knapsack we break items, but as you can see here we didn't break the item if we had broken items then greedy would have give (80 + 19) => 99

@atharvameher5880 6 месяцев назад

thanks...was confused@@codermal

@abdallaalhag4425 6 месяцев назад

understood, had to write it out to understand the tabulation logic but that made both space optimization a lot easier to understand.

@nagasrikuncharapu3736 5 месяцев назад

I was able to write top down approach on my own. It's all because of the previous lectures. Thanks to you brother.

@polycarpvegas9446 2 года назад

POV : Educated guys do not steal 💀💀

@rameshsharma3639 4 месяца назад

No doubt why you are most loved teacher !! HATS OFF. ---> one array space optimization was something out of the box

@anshulsomvanshi9483 Месяц назад

1D Array approach was mind-blowing !! As always, thanks for the great lecture !!

@AMANKUMAR-eq6sq 2 года назад

I bet no one in the entire you tube teaching community can match your style of teaching and applying brain. Last part of space optimization really blew my mind.. Hats off Sir!!

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@ankita716 Месяц назад

understood! you are an extra ordinary teacher and make everything doable for us as well. thank you so much

@ravikjha07 2 года назад

It was amazing !!! I was trying it by myself but couldn't do the optimization in one Single Array, but now Understood !!!

@adityahirwani1672 2 года назад

Simplest explanation ever , and the way you had arranged the DP problems is really outstanding its makes every problem so simple. Thankyou 😊

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@aakashyadav8142 8 месяцев назад

Your effort for optimization as tremendous . I have no word to praise and respect you . Salute you sri.

@user-oz2eu7rs8v 6 месяцев назад

Best explanation.Just loved it Thanks a lot striver for making such series .✌✌

@sayakghosh5104 2 года назад

Mind blowing space optimisation....Hats Off Bhaiya!!!! Understood!

@amanbhadani8840 2 года назад

One array optimization is just next level thing. This shows how deep you understand,exactly what previous values our code is using while computing our present value.This is only visible if we manually do a dry run in tabular form .

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@stith_pragya 6 месяцев назад

UNDERSTOOD............one row optimization is an amazing thing.........Thank You So Much Striver Bhaiya for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@koushalsharma7041 2 года назад

Absolutely loved the idea of space optimization to a single array. Understood !

@aryanyadav3926 2 года назад

Really the space optimization using only a single row was wow, which I realised after dry running of course!

@tonystark-oq3mm Год назад

Man that lecture was amazing from start to end ! The final space optimization that really was like icing on the cake ! Thanks striver Understood!

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@drishtirai864 3 месяца назад

Understood !! The single array optimization was mind-blowing.

@ssshwanth 2 года назад

Hi bro, before starting this series i had zero knowledge in dp and searched for lot of videos bt no one said right pattern, bt u did for space optimization ,tricks and explained why not greedy works? We will appreciate ur work Thank you Learner 😁

@gem13259 9 месяцев назад

Understood!!!!!!!...Thanqew so much Striver u made concepts easy......space optimization with 1array was incredible💫

@AdityaKumar-be7hx Год назад

This was awesome! No one ever explained when can we go from the other end in loop. This is the best explanation.

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@ugempireninjaaaaaahatori6755 7 месяцев назад

the last concept was just like a thrilling and amazing part , love you striver.....soon we will meet

@ONLYFORCF 2 месяца назад

really amazing video didnt find such video anywhere else

@Abcd-jt1qs 14 дней назад

I could solve the recursive, memoisation, tabulation and space optimisation approach with 2 vectors on my own.. So thankful to you striver. The last space optimised method was very nice. Understood and a big big thank you :)

@user-sw3oo9fr5l 23 дня назад

Hello Sir this question seems to be a very simple and direct one when read for the first time if you have basic idea about DP on subsequences. But when you code it and visualise using the 2D DP array / matrix and check the test cases, only then one is blown away by the beauty of it. Also the manner how the previous Row is enough to evaluate maximum value adds to the class and excellence of the question !

@ajith4249 9 месяцев назад

Thank you striver. Solved by myself in Tabulization and memoization and space optimzation❣

@hoordealer 2 года назад

Awesome bro. Such RU-vidrs like you and other also are support for us. Thanks for your every video.

@ayushagrawal3254 2 месяца назад

You content is so so good. Understood very well.

@AbdulKadir-bh3el 2 года назад

Its been a year im learning DSA, Most of the time ive skipped this problem due to awkward expln but now i can't leave it. Thnxx man😇

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@ankitaKumari-br1oc Месяц назад

Wonderful, Knapsack was never this easy before 🤩

@DivyaKumari179 29 дней назад

Thanku for this amazing series. And as always #UNDERSTOOD.

@harshitabhatt4301 Год назад

yes, 1d array optimization technique was amazing!!

@dadidivya8663 Год назад

Wow, Doing this on my own, I knew I have got better. Always assumed knapsack to be very difficult. Now it is a piece of cake. Thank you Striver!

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@KulvinderSingh-pm7cr Год назад

Gazab bhai, understood, only this video explains this single array approach that too so succinctly

@travellercoder7298 2 года назад

Underrrrrrssstttttooood now seeing the length of string u can guess how much I loved this thnx man..

@radharamamohanakunnattur3035 Год назад

Loved the one array approach

@ayushanand8926 3 месяца назад

Amazed by the one-dimesional spaced optimzation

@muskanchaurasia1532 8 месяцев назад

It was just mind-blowing👏.

@logeshv2125 26 дней назад

Striver, that's super cool logic for using a single row✨

@MukeshKumar-cc3uh 4 месяца назад

Understood ❤. The 1 array space optimization part was amazing, it unlocked one more part of my brain.😅

@paveshkanungo6338 8 месяцев назад

Understood! Space optimization is mind blowing🤯🤯

@radhakishoriiiiiiiiiii7348 7 месяцев назад

35:54 LOL Awesome walk through to the intuition for optimizations.. thanks striver

@hrushikesh-1914 9 месяцев назад

Thankyou sir for very clear explanation and energy. Understood sir

@prashantrajaji9550 6 месяцев назад

You are a great teacher....I love you!!!

@aasthaaggarwal8909 2 года назад

The best ever explaination of DP present on Earth is yours.

@mriduljain5801 11 месяцев назад

wonderfull. that 1-d space optimization was chumeshwari woww!!!

@ritikshandilya7075 25 дней назад

Thankyou for great explanation Striver

@sangeetasharma8574 Год назад

Amazing Explanation -understood the single row optimisation -Thanks Striver

@user-or7xr2mt3o Год назад

This is by far the best video that I have watched on 0/1 knapsack...even though I was able to do recursion + memoization as well as 2 row space optimization on my own....this further optimization to one row blew my mind !! AMAZING

@takeUforward Год назад

Every video on TUF post 2021 will be the best version of all videos you see :P

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@raxxpatt 10 месяцев назад

@@MadhavGupta-fi2tu bhai chill kar!! ..kitni lega yaar uski .. itna dhundega tho bhagwan mil jayenge .. thand rakh thodi 😄😄

@tanujchaniyari6005 2 года назад

I have seen so many DP series, but boy oh boy your videos are next level thank you so much Raj bhaiya

@satyaveernayak3462 Год назад

i loved it really ,i totally understand and the way you made it easier thanks

@adityaanand8473 2 года назад

Totally loved the one array optimisation.

@suhartabanerjee9177 2 года назад

Great Sereies bro. You are doing a great job. Gradually now I am able to build logic and write the code on my own. DP certainly started to look much more easier than before. Please continue this series and finish it up as quickly as possible. We all are counting on you and we know we will learn a lot from you.

@MadhavGupta-fi2tu Год назад

why in tabulation base condition is from i=w[0] ?

@VishalKumar-lw3yh 10 месяцев назад

@@MadhavGupta-fi2tu if we come to index 0 let's say the the weight there is 5, and the weight we can take is 3..so we will discard it any value which is lesser than 5 now say if the weight we can take is 9..so from 5 to 9 we populate our dp table with val[0]