MoonKnight9031's blog

By MoonKnight9031, history, 4 months ago, In English

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.

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MoonKnight9031 (previous revision, new revision, compare).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

you need to memoize for the variables which changing in the recursive calls.

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

One liner

Spoiler

Explanation

Spoiler
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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