Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Jahid's blog

By Jahid, 6 years ago, In English,

Hi Everybody !!! In solving dp problems, I have seen that it is easy to solve the problem recursively. But , recursive solution has so many function calling and dependencies.

There are many problem where recursive solution only produce TLE so there needs a iterative solution.

In the following problem, "There is no recursive accepted solution"-Moderator said. http://www.lightoj.com/volume_showproblem.php?problem=1232

or

http://paste.ubuntu.com/9639366/

So I need iterative as the only solution. While doing this in case of this problem I have found that it is difficult to transform recursive solution to iterative solution. I think there should be any general algo in this case.

Can you help me by give me any tips that you follow generally in that kind of transformation?

Thanks in advance.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In that case , I always try to reduce the memory first . Then try to reduce the loops. and try to maintain the memory in O(n) complexity. I think all iterative procedure has a O(n) memory complexity solution. I am not sure but I have seen. I'll be pleased if you share yours.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can't give us link to lightoj because one should be logged in to read problem statement. Copy-Paste problem statement into patebin.com or similar site. It is solution for your problem?
To "unroll" recursion you should imagine the order of operations, then call your DP function in this order.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I have got this tutorial as helpful for iteration to recursion:

https://www.topcoder.com/tc?module=Static&d1=features&d2=040104