### MoonKnight9031's blog

By MoonKnight9031, history, 4 months ago,

In some Dynamic Programming Problems, I am able to code the recursive solution but I find it hard to convert it into Top-Down DP or Memoization. For example :- This is a problem from yesterday's Codechef Starters Contest:- Problem Link

Below is my Recursive Code to the problem:-

My Code

It would be helpful if someone could suggest me some ideas on how to do so.

• -5

 » 4 months ago, # |   0 Auto comment: topic has been updated by MoonKnight9031 (previous revision, new revision, compare).
 » 4 months ago, # |   0 you need to memoize for the variables which changing in the recursive calls.
 » 4 months ago, # |   +9 One liner SpoilerTopological sorting of dp statesExplanation SpoilerIn your recursion, what is calculated first should be calculated first in here as well. When we call dp(0,n) in recursion ,(0,n) is calculated at the end, so even in for loops it should be calculated at the end. Now for this example Two variables, two loops, such that last state is 0,n for loop decreasing to 0 for loop increasing to n Copy paste your recursion 
•  » » 4 months ago, # ^ |   +3 You didn't understand his problem. He's not asking how to code a bottom-up DP.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Got it. So @MoonKnight9031, I will give it another shot.. When you write recurrence, try to avoid including array/vector as a parameter to the recursive function(you can keep them globally) or let's ignore them for now. Now let's say your recursive function has k parameters, then initialize a table globally [][][].. k boxes. Size of ith box = number of different values ith parameter can have. Now you can fill your table with a value, which is a never possible value for any of your dp. Then you can have at start of recursion a check, if value exist in table return it else store value in table. If you find that space is too much, maybe you need to rethink your recurrence or try to convert it to for loop dp as per my first comment and then use space optimization, if possible. This submission will show you the whole process 143442881
•  » » » » 4 months ago, # ^ |   0 Thanks, this was really helpful.