Dynamic programming--tabulation method bottom up

Question

Just practicing some general problems on dynamic programming.Problem is I am unable to think of tabulation or bottom up approach for most of the new type of problems other than common ones.I am trying to get the naive recursion first then using memoization easily to optimize.Can someone who is in good peak of programming at this moment let me know how to get some idea of tabulating easily?..For example take coin exchange problem.

Comments

First get a clear recursive solution. Better if you apply it also. See if it's working.

Now time to make it efficient. Search for overlapping subproblems. Drawing the recursion tree will help. You have to find subproblems which are being calculated repeatedly. This is the most important step. 

If you can't find overlapping subproblems, then using dyanmic programming won't improve any efficiency.

Finding the overlapping subproblems is the MOST important step.

---

Tabulation/bottom works by filling the table from 1st entry to last entry and generally the last entry will be the final answer.We dont need to use recursion here as we will be filling each entry from bottom to top.Mostly for loops are used to fill the table.No recursion overhead is involved here.But we might end up solving some subproblems that are not required.

Other approach for DP is top down/memoization,which involves recursion and it works similar way as naive recursion,but before solving any subproblem,it will first check in table whether this particular subproblem is already solved or not.If already solved,then use the result,otherwise solve the subproblem and store its result.HEre we will solve only those subproblems which are actually required.

---

thanks guys....but I am facing problem mainly in tabulation process....I am getting the recursion solutions then easily memoizing it and the program works fine...but bottom up approach I am not getting directly...

---

See second sol. here https://www.geeksforgeeks.org/longest-common-subsequence/

Also second sol. here:-   https://www.geeksforgeeks.org/knapsack-problem/

These are based on bottom up approach

---

hmm..thanks rahul...I am following geeksforgeeks...really good programming problems...