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.

Auto comment: topic has been updated by MoonKnight9031 (previous revision, new revision, compare).you need to memoize for the variables which changing in the recursive calls.

One liner

SpoilerTopological sorting of dp states

Explanation

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

You didn't understand his problem. He's not asking how to code a bottom-up DP.

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

Thanks, this was really helpful.