How do I create an efficient Dynamic Programming iterative solution if I can develop a recursive solution for the same?
Edit 1: I have seen several problems on spoj where I can design a recursive solution O(2^n) but those solutions generally time out. After looking into the solutions of the problem I found that an iterative solution with O(n^2) mostly works.
So, I am just asking is there a general process to create an iterative solution from a recursive one?
If you can come up with some sample Q or something, it’d be nice, as I feel Q is quite broad. But I will attempt to clarify your doubts.
Lets take example of Fibonacci numbers. We all know the recursive approach is-
return fib(n-1)+fib(n-2); //assume fib to be the function.
In this function, we use if-else to check for base cases (like 1st Fibonacci number being 1 or etc. as given in problem or found out by us), and make the function call itself until base cases are reached (so it can finally start computing).
The dynamic approach is conceptually same. We assign initial values of table the base values.
Eg-
int fib[n];
fib[0]=1, fib 1=1;//assume fib to be a 1-D array, not function here.
Now, just like recursion approach would repetitively call itself to return value of fib(n) [by computing and finding fib[n-1], fib[n-2], fib[n-3]…fib 1 etc.)
In dp, we would make a loop which would use past values of table to compute future values.
Eg-
for(I=2;i < n;i++)
fib[I] = fib[I-1]+fib[I-2];
Starting from I=2, this loop would directly start computing the values and we would save a lot of time (which is lost in function call and re-computing same sub-problems in case of recursion)
The difference may seem little, but the effect on time taken is HUGE. I highly recommend visiting geek for geek’s first 2 articles on dynamic programming. I think they will surely help you!
As your question has been answered right, but i want to add one more thing that there is no shortcut to getting success. Only you can do is to practice more and more in these type of questions. DP is seems to be difficult un till you would not find the exact recursive function of solving that.
And most important part of DP is table filling that will need practice and visualization of how you relate the solution from previous stored value.
Keep coding and practicing.
You don’t even need to make your recursive solutions iterative many times. You can just store the results and when you need to calculate that result just look at the place where you stored that result.
This might help.