Ways to Solve DP 2
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 have seen the Top down approach to solve the DP problem . Now we will see the other approach to solve the problem
Bottom Up Approach
- It is also called as tabularisation .
- This is generally harder to think and visualize in one go but with little practice and patience anyone can master it .
- The basic idea here is to turn the recursive solution around get a bottom up solution instead .Since we already know the subproblems we can start building from the base case and move up to cover other cases iteratively.
Lets understand this by taking the same fibonacci problem again . So here we first focus on the base cases ie we know for fibonacci problem
fib(0) =0 , fib(1) =1 ,fib(2)=1 and so on …
So we iteratively start from the base case and use the already calculated result to calculate the further result . Lets look at the solution to this problem using bottom up approach.
Since we are iterating here from 0 -n once, our time complexity will be O(n) and our space will also be O(n), as we have created a 1D array from 0 to n. This makes our current solution comparable to the top-down solution, although without recursion. This code is likely easier to understand.
I hope now identifying the DP problem and two approaches to solve the DP problem is clear .Lets look up Knapsack problems in our next post .
Till then Stay Tuned !
