01 Knapsack Tabulation Dynamic Programming | How to build DP table

[@sakthim7160]

dp[i][j]= max( dp[i-1][j], profit[i-1]+dp[i-1][*j*-wt[i-1] ) you specified W instead of j while including the element in final else statement.

[@techdose4u]

Yea right. It should be j.

[@amitkumargupta6722]

@@techdose4u Its okay...concepts are more important than code..

[@Nieobliczalny1000]

@@techdose4u What if j i wt[i-1] will be smaller than 0? Generally index out of bound?

[@savostyanov]

​@@Nieobliczalny1000 We prevent this case in this line if (i == 0 or j == 0) dp[i][j] = 0

[@JitendraSingh-qd7jk]

Stop copying and pinning aditya verma's code Sakthim

[@vend57]

saw an algoexpert ad before the video. Am I buying that course after knowing that Techdose has covered 5 X more problems than Algoexpert ?

[@dhananjaychoudhary7836]

Thanks a lot man. This is my 4th attempt to understand knapsack DP and also the last one.

[@techdose4u]

Nice :)

[@Neonb88]

Congrats! Never quit!

[@MohamedSayed-wl5cj]

Best video on KZbin explains Knapsack problem with clear way,thanks

[@techdose4u]

Welcome :)

[@bhargavsai2449]

within 2 or 3 yrs you will have millions of subscribers, great channel.

[@techdose4u]

Thanks :)

[@aryankumar87771]

the sheer clarity of the explanation

[@theghostwhowalk]

Never knew about heap Vs Stack memory thanks much for in-depth explanation!

[@techdose4u]

Welcome :)

[@ismail8973]

Your intuition explanation is on another level

[@34_harshdeepraghuwanshi98]

Sir your explanation is too much above from paid courses and also in your video i never get a doubt or if i get then you always cleared doubt by yourself later in video thanks a alot sir for providing free quality education 🙏🙏👍👍👍👍👍

[@techdose4u]

Welcome bro :)

[@dionisorules]

Thanks for presenting this problem so orderly, going from the decision making tree, to the recursive approach to end up translating that into the tabular iterative approach. Now this is no more black magic for me, but step by step sound reasoning. Like others said your capacity to explain these complex solutions is just brilliant and far superior to paid courses.👏🏼👏🏼👏🏼

[@mikekibet1786]

Another masterful explanation. If I could subscribe twice, I would.

[@techdose4u]

❤️

[@vaibhavkumargautam]

This is the best explanation i ever came across..

[@sorajkandari9603]

How can u be so clear in every single word u say. awesome bro !!

[@gowthamsankaran67]

Thank you so much for the explanation. I was struggling with converting recursive to iterative code. This helped me a lot.

[@techdose4u]

Nice :)

[@prathamanand1037]

this was a bomb video, better than everything I have ever seen

[@techdose4u]

❤️

[@mallikarjunareddy4848]

Thanks for the explanation. It gives me an idea on how to come up with bottom up solution for dp problems . It would have been great if you had covered why we are considering items from right to left. I sat for couple of hours thinking about it and finally, I could understand the benefit of considering items from right to left over left to right

[@niksgupta36]

Can you mention those here? I think he sorted the profit array in increasing, hence working from right to left.

[@pradnyamahadik5540]

Wow...really amazing explanation💯

[@namanvijay3514]

great series , following this one 👍

[@techdose4u]

Great ❤️

[@mahendrasuthar7354]

amazing bhai kya samjhaate ho mjaa aa gya thanks a lot.

[@ashvinimeshram5242]

Your alll vedios are really nice.and it help me alot in my concept buliding thank u so much🙏🙏🙏🙏really good content

[@techdose4u]

Welcome :)

[@salilkumar6500]

Your explanation is crisp,clear n short. Very helpful to me . Keep the good work going on man,

[@sarvarjuraev1376]

Thank you very much for the accurate explanation.

[@dhanashreegodase4445]

best video i have ever seeen..excellent..thanks alot

[@techdose4u]

Welcome :)

[@jayanthjj]

Thanks for this Great Video series!

[@nknidhi321]

Thank you..🙏❤️

[@techdose4u]

Welcome :)

[@nimishkumar9779]

Thanks a lot! The best explanation.

[@techdose4u]

Welcome :)

[@codingexception6502]

Your explanation is really good.

[@adim1212]

You and Aditya Verma both have explained DP thoroughly and both have messed up at same concept i.e. Mistaken Bottom-Up as a Top-Down approach. Did both of you shared same notes or what???

[@hiteshchopra9181]

Bro I was literally finding the same in comments as I was also confused haha. But no doubt both of them teach very very good.

[@debdattabiswas4902]

excellent explaination.

[@garimakumari4346]

woow man really great..nice job

[@techdose4u]

Thanks

[@MadForCs16]

Hello sir, I have one doubt, in this process we're actually moving from bottom to up ....like n=0, W=0. then why are we calling it *top-down* approach? It should be called *bottom-up*

[@techdose4u]

You are right. I had made a community post regarding this. Wish you were there 😅 But yea, it's bottom up.

[@大盗江南]

amazing video, thank u

[@samarasimhachalla3509]

When deciding about which one to go ahead with Memoization or Tabulation methods. Try to identify the no.of values in the DP table or array that is required to solve the problem. If the number is very less compared to the total size, then go ahead with Memoization for better time complexity because in the Tabulation method it'll compute the whole table, then give you the output. And yeah, if the number of values that need to be computed in the table or array, is not very small when compared to the total size, then yeah go ahead with tabulation. Credits: GFG

[@amansingh.h716]

THANKS SIR

[@techdose4u]

Welcome

[@ankitparashar8730]

I have solved most of dp problem using recursion and memoization .i felt memoization dp is easier than tabalization . Should I learn tabalization dp ???

[@venkatadokku9190]

Nice share. Can you point some questions associated with this concept ? Appreciated.

[@techdose4u]

Subset sum problem

[@abhigyansharma9108]

Love You Sir

[@techdose4u]

Thanks 😊

[@rangapavankumar79]

How come 'w' in last line is it 'j' b'coz 'j' is capacity of bag?

[@techdose4u]

It will be j because j is current capacity.

[@Neonb88]

Wait his handwriting on a computer is so pretty. That's just the first thing I noticed. Obviously it's a good tutorial video, too

[@Cloud-577]

Thank you

[@rishviks8987]

Sir I'm good at memoisation but I don't have any idea about tabulation coz I nerver used it. Should one know both of them?

[@techdose4u]

Better to know both.

[@srikantsharma6430]

Well explained!

[@techdose4u]

Thanks

[@naman_goyal]

Very nice

[@techdose4u]

Thanks

[@KhushiYadav-fo9ul]

Please correct me if I am wrong , the memoization is a top- down approach and tabulation is a bottom up approach .....

[@techdose4u]

While it looks just the opposite but you are correct :)

[@kuntipatidar5191]

how your concepts are so strong?

[@priyank907]

Patience and practice

[@adityaojha2701]

We start filling table from smaller value to greater value, so this become bottom up approch. Am I right??

[@Rasheed21]

Not really. Tabulation/Iteration is Bottom-Up even if you interate in decreasing order. Recursivion+Memoization is Top-Down even if your recusion is in increasing order.

[@heedererroger9324]

your approach to get maximum value is direction which is from right to left. But your table structure is left-top to right bottom to find maximum value. It's confusing... am I misunderstanding?

[@imukai]

I get that this method gives you the total profit at the end of the table -- but how do you determine which of the elements in the set were selected to arrive at that sum?

[@smitkarwatkar03]

use a prev array which will store the indexes of each optimal step. at the end you would get all the elements in your optimal solution

[@manoranjaniiit]

too good

[@techdose4u]

Thanks :)

[@santoshr4212]

Friends, can someone explain in which case memoization will be useful because unlike Fibonacci I dont see a case where same value/computation can be repeated because in each case weight may be different

[@biswajitghosh9315]

Love you bro

[@piyushkumar-wg8cv]

You have messed up the indexes.

[@_SajjadHossainTalukder]

A bottom-up algorithm "starts from the beginning," while a recursive algorithm often "starts from the end and works backwards" . That's why recursive algorithm is known as top down . U wrongly interpreted this top down Approach. It may be Bottom-Up approach. Please Make it clear.

[@andresdallarizza1526]

fucking legend lov u adore u

[@techdose4u]

:)

[@tech_wizard9315]

Please make a roadmap for fresher to crack google in 6months

[@learnersparadise7492]

You copy pasted content of Mr Aditya Verma in English, just...even his calling of bottom up as top down is copied man....do some original work please 🥺🥺

[@tvrao123]

too lengthy explanation

[@techdose4u]

It was basics so it went long.

[@Dryicicles]

lmao then shut up and dont learn

[@manishkumartyagi1815]

Looks like copied from the videos of Aditya Verma :D , exactly same.......... hahahahahaha

[@vigneshvicki7020]

i almost gave up trying to understand DP in tabulation, but Finally I did understand, Thank you very much bro🥹

[@techdose4u]

Great :) welcome 😃