When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

MoonKnight9031's blog

By MoonKnight9031, history, 2 years 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

| Write comment?
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

One liner

Spoiler

Explanation

Spoiler
  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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