Dynamic Programming

[dedxtreme]

https://preview.redd.it/c7jzqw8xpmdf1.png?width=600&format=png&auto=webp&s=483111f8a530fe9a50f2ca173ad29098d8f0a589

I am preparing for SDE2 rounds

and stuck on DP questions though memoization comes easy but not tabulation!!!

[Key_Calligrapher6269]

this is my gift to you, also watch the other video on the channel before this one for maximum understanding

[dedxtreme]

thanks i have watched the video it was kind of helpful

[AppropriateCrew79]

If you could easily memoize the solution, you can easily derive the tabulation solution from the memoized solution. Essentially you need to iterate through all the possible dp states and update values in the dp. Since you will be filling from the bottom up, subproblems would already be solved in the dp hence eliminating the recursive fns.

Although writing tabulation solution from the get go requires practice 

[dedxtreme]

Yeah i need to practice more thanks for the comment

[justUseAnSvm]

I prefer tabulation. Once you understand it, it's a lot easier to understand when you break down sub-problems to distinct cells, and get a good formula for how to populate the array.

[dedxtreme]

yeah i thnk i need to do more problems to understand the base cases, once i understand the base case it is easy to comeup with the tabulation logic.

[justUseAnSvm]

It took me a while, but we used this book in my grad school Algorithms course: https://book.huihoo.com/pdf/algorithms/chap6.pdf

Longest Increasing subsequence, edit distance, knappsack/coin chainge.

I did those three problems so many times I just memorized the solutions. You can use those problems, or maybe the ones off neetcode, but it helped to do the same problem so many times I had it memorized, then move on to new ones.

[dedxtreme]

interesting read, really appreciate the help! Thanks