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.
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.
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.
An example of recursion "unrolling" for problem folding.
Thanks goo.gl_SsAhv, problem is here ans my recursive solution is here and my iterative solution is here You have given a technique at the last part of your comment. It seems good to me bro.
I have got this tutorial as helpful for iteration to recursion:
https://www.topcoder.com/tc?module=Static&d1=features&d2=040104