OJ Board

Can anybody tell us about some cool way to convert any recursion to corresponding Dynamic Programming approach?

I have always seen a connection between them. I also know that there is a recursion behind every Dynamic Programming. But i know of no exact way to converting one to another.

Is there any way to do this??? What do you algorithmist guys think? How do you convert recursion to DP???

Dynamic programming simply caches intermediate results whereas recursion does not.

When the recursive function returns, all of the intermediate results are lost.
So, for the same input twice you get to do all of the steps over again!
What do you think about that?

Adding a cache to your recursive solution would make it dynamic. Then the function will remember where it has already been...what it has already calculated.

That way the function does not have to do all the recursive steps over again for each input (especially if the input is the same that has been processed before! But you know it applies to different input, right? If you counted a million marbles, and I gave you one more & asked you