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

[@takeUforward]

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]

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]

I checked the like count has crossed ever 7000😎

[@iamnoob7593]

understood

[@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.

[@shubhankarnikam-x9g]

yes same happen with me

[@pragyajha5609]

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

[@ayushsharma7946]

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

[@GManiKarthik]

After you dropped the problem statement, I was like, "Let's crack this!" 🧠 So, I started with recursion 🤔, then jumped to memoization 📚, tabulation 📝, and finally space optimization with 2 arrays 🧳. Everything was going smoothly, and I thought, "Mission accomplished, time to skip the rest of the video!" 🎬... But wait-single array space optimization 😱?! My curiosity levels went from 0 to 100 real quick 🚀, so I continued watching. And man, when you explained space optimization with just one array, I was like 😲. The way you broke it down was pure magic 🪄-I was hooked! 🔥 You are the LEGEND of DSA-especially when it comes to DP, Grids, and Trees . Seriously, if there's a DSA Hall of Fame 🏆, you're already there! #Understood ✅ #DP19 #HatsOff 👑 #Striver 🙌

[@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]

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]

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

[@Infinity-squre]

Just using a single array😮, that blew my mind... Thank you striver❤

[@anmolmajhi225]

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]

@@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

[@KrishnaGuptaTech]

Wow 1 array optimization was absolutely amazing, thanks u striver, definitely understood !!!

[@yamanaggarwal6391]

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] ?

[@parthdurgude2617]

understood!!! I solved the problem without even watching the video, and when you were explaining space optimization using only single vector, it was an 'EUREKA' moment for me as I understood before you explained it!!! The space optimization is too good! thankyou bhaiyya!!!

[@paridhijain7062]

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) .

[@YashSaxena1-s6l]

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

[@MrGohel-ni2py]

@@YashSaxena1-s6l I advice you to watch dsa playlist from striver , in take you forward website there is a to z dsa section where each topic question and solutions are given just search that topic in this youtube channel

[@Himanshhhhxu]

I'm here third time watching this video, and everything is worth it❤❤ totally understood 💥🔥 you are a genius

[@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]

@@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

[@StudyMan-pf9tn]

Understood and was able to see 1 array optimization once you hinted about it at middle of video. i did cross varify at end and my approach was right. Thank you for best content striver

[@AMANKUMAR-eq6sq]

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] ?

[@omeshdeoli9475]

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

[@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............🙂🙏

[@anshsaxena7297]

Understood , this is simply perfect! 1D space optimization ---- perfect, simply perfect.

[@sonukumarram1880]

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

[@harshitpatil6138]

Space optimization from 2 arrays to one is really insane😏. This man can only do it👐👐

[@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

[@vibhavsharma2724]

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

[@parthsalat]

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

[@techmelon7]

my DAA professor taught this question with tabulation method. but after watching this dp series now I got the intuition behind that approach!

[@meetsoni1938]

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.

[@shubhankarsharma154]

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

[@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!!!!!!

[@jaiminsolanki5478]

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

[@rameshsharma3639]

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

[@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!!!

[@sangeethagopalan301]

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

[@AbdulKadir-bh3el]

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] ?

[@stith_pragya]

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

[@shineinusa]

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]

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.

[@harshugamer7776]

I solved this using memoization, tabulation, and finally space optimization. I was about to skip the video, but I was casually watching the final code, and I was like, 'WTF, with a single 1D array'🥶

[@aryanyadav3926]

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

[@harshitgupta7496]

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

[@itsaryanb9316]

Loved the Single Array space optimised approach !!

[@nagasrikuncharapu3736]

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

[@balwantyadav724]

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

[@MadhavGupta-fi2tu]

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

[@Arindom6]

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 !

[@Ani_86_]

The single vector optimization was wonderful 🔥😅

[@sharan7504]

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

[@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] ?

[@AyushMishra-b8w]

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

[@souravkumar-eb1wz]

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] ?

[@Abcd-jt1qs]

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 :)

[@Saurav_Kumar514]

1D Array optimisation is really Awesome 🔥❤

[@MadhavGupta-fi2tu]

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

[@abdalla4425]

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

[@codermal]

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]

thanks...was confused@@codermal

[@viveksingh_01]

thanks I was thinking same thing

[@vibhanshugarg3603]

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

[@jitendrasinghsola]

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] ?

[@anshulsomvanshi9483]

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

[@priyankasati8308]

Awesome, seriously love the last 1d optimization.

[@MadhavGupta-fi2tu]

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

[@drishtirai864]

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

[@polycarpvegas9446]

POV : Educated guys do not steal 💀💀

[@radhakishoriiiiiiiiiii7348]

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

[@amanbhadani8840]

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] ?

[@ranasauravsingh]

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

[@aakashyadav8142]

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

[@moksh7130]

A normal person cannot even think of this man, unreal observations

[@Happy-tf7se]

DP used to be a nightmare, I sort of ran away from it but after following your playlist it seems something approachable. I am soo happy I am able to solve these on my own.

[@SaurabhMishra-e8m]

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]

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

[@MukeshKumar-cc3uh]

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

[@ankita716]

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

[@gem13259]

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

[@RohitKumar-dy2gc]

loved your one array optimization technique❤❤

[@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] ?

[@sayakghosh5104]

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

[@ugempireninjaaaaaahatori6755]

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

[@paveshkanungo6338]

Understood! Space optimization is mind blowing🤯🤯

[@ssshwanth]

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 😁

[@subhadrosamaddar6336]

What the level of content! Hats off bhaiya for your effort.Thanks you a lot.I am also in the same college of you - JGEC. You are my motivation and spirit of learning coding.

[@logeshv2125]

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

[@yashkhatwani3198]

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

[@DivyaKumari179]

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

[@KingAstraVerse]

Ohh bhai gazab socha hi nhireverse vala space optimization

[@nileshdesai5218]

solving in 10min before watching lec its just magic of striver

[@ankitaKumari-br1oc]

Wonderful, Knapsack was never this easy before 🤩

[@24deeshankbatra38]

In every question where we were dependent on just the single value of prev array I was thinking of this single array approach and now i'm relieved that i was thinking correct :)

[@shuvo9131]

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] ?

[@lourduradjou182]

Loved the one array approach...stunning striver

[@ajith4249]

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

[@mriduljain5801]

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

[@souvikbiswas284]

really loved that 1 row optimization part😎😎✌✌

[@KulvinderSingh-pm7cr]

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

[@lexeve5298]

Amazing space optimization ever seen in Dynamic programming, these type of lectures motivates us to work hard, Thanks bro

[@ravikjha07]

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

[@ayanghosh7635]

I just solved the problem all by myself.. all thanks to you bhaiya!! U r the best teacher i ve seen so far ❤️

[@MadhavGupta-fi2tu]

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

[@studynewthings1727]

understood😃. Yes I loved the single 1D array optimization.

[@anuragtiwari9793]

at 32:22 on line 18 why sir put everything on the first row as val[0]...because there will be cases when we also cannot have the first item if capacity is too less...there should be if and else block like in the memorization base case

[@sanonas7865]

The last 1 array technique was nice one . I haven't think for more optimization

[@vipul0710]

striver.. literally uh kidded it..💥🔥 last space optimization wass 🔥 loved it ❤️

[@jidgesanathkumar8038]

All are born to go forward And then there is you, who was born to take us forward Living legend Striver sir...🙇🙇

[@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] ?

[@sujalgupta6100]

Understood and thanks Striver Bhai for making me a good thief. Now , I can finally steal from my neighbor's house with maximum value of items.

[@takeUforward]

Haha

[@coder_RJ]

best video of knaosack stuck in this from 2 days in space optimization

[@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] ?

[@ayushgautam8000]

Understood And mad respect for Striver !!