01 Knapsack Tabulation Dynamic Programming | How to build DP table

This video explains the concept about how to approach a dynamic programming problem to solve using tabular DP. I have explained the concept using 01 knapsack as an example problem.I have shown the concepts and intuition in the beginning about building a table.I have also shown how to convert a recursion code to iterative code by using simple observations.At the end, I have shown the process to write Dynamic Programming code for 01 knapsack problem.If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
USEFUL LINKS:
01 Knapsack Recursion: • 01 Knapsack using Recu...
01 Knapsack Memoization: • 01 Knapsack using Memo...

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

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

[@bhargavsai2449]

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

[@techdose4u]

Thanks :)

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

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

[@ismail8973]

Your intuition explanation is on another level

[@aryankumar87771]

the sheer clarity of the explanation

[@theghostwhowalk]

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

[@techdose4u]

Welcome :)

[@vaibhavkumargautam]

This is the best explanation i ever came across..

[@MohamedSayed-wl5cj]

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

[@techdose4u]

Welcome :)

[@sorajkandari9603]

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

[@sarvarjuraev1376]

Thank you very much for the accurate explanation.

[@jayanthjj]

Thanks for this Great Video series!

[@mikekibet1786]

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

[@techdose4u]

❤️

[@salilkumar6500]

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

[@codingexception6502]

Your explanation is really good.

[@pradnyamahadik5540]

Wow...really amazing explanation💯

[@gowthamsankaran67]

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

[@techdose4u]

Nice :)

[@nimishkumar9779]

Thanks a lot! The best explanation.

[@techdose4u]

Welcome :)

[@debdattabiswas4902]

excellent explaination.

[@mahendrasuthar7354]

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

[@vigneshvicki7020]

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

[@techdose4u]

Great :) welcome 😃

[@prathamanand1037]

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

[@techdose4u]

❤️

[@user-oy4kf5wr8l]

amazing video, thank u

[@namanvijay3514]

great series , following this one 👍

[@techdose4u]

Great ❤️

[@dhanashreegodase4445]

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

[@techdose4u]

Welcome :)

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

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

[@srikantsharma6430]

Well explained!

[@techdose4u]

Thanks

[@garimakumari4346]

woow man really great..nice job

[@techdose4u]

Thanks

[@Cloud-577]

Thank you

[@nknidhi321]

Thank you..🙏❤️

[@techdose4u]

Welcome :)

[@abhigyansharma9108]

Love You Sir

[@techdose4u]

Thanks 😊

[@amansingh.h716]

THANKS SIR

[@techdose4u]

Welcome

[@biswajitghosh9315]

Love you bro

[@naman_goyal]

Very nice

[@techdose4u]

Thanks

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

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

[@manoranjaniiit]

too good

[@techdose4u]

Thanks :)

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

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

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

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

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

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

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

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

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

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

[@piyushkumar-wg8cv]

You have messed up the indexes.

[@andresdallarizza1526]

fucking legend lov u adore u

[@techdose4u]

:)

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

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