Ways to Solve DP 1
This is in continuation of our previous post in the series .If you have not seen that please have a look to my earlier post in the series
So in previous post we discussed ,how to identify the DP problem .Now lets looks into the first way of solving the identified problem.
Top Down Approach for solving DP problems
- Its also called as memoization
- The basic idea here is to traverse the recursive call from top to bottom and eliminate the extra overlapping recursive calls by first checking whether they are already computed or not.
To understand this better lets take example of fibonacci problem . We will try to write out the fibonacci recursion from what we already know
We know fib(0) = 0 , fib(1) =1 ,fib(2) = 1 ,we can see a pattern over here
fib(n) =fib(n-1) + fib(n-2)
Now here first we will try to solve it through recursion .
Now if we trace out the recursion in the recursive tree for a call of n =4 it will look like this
We can see the Complexity of the approach as follows
T(n) =T(n-1) + T(n-2) + O(1)
T(n) = O(2^n)
So its and exponential complexity problem ,lets try to analyse it further
We can see there are many subproblems that are overlapping ,so in order to efficiently solve this we use DP here .So we will maintain an additional memory in the form of dp array to save the result of the function calls ,and we will only call the recursive function if we have not computed the recursive call until now .
Lets walk through the Optimized Code now .
So now if we will see ,there are no more extra recursive calls .So it will significantly reduce the time complexity to O(n).
Next we will discuss the other approach to solve the DP problem .
Stay Tuned and Happy Coding !
Follow below link to move on to next.
