not able to understand the difference between memoisation and top down
and
memoisation shouldn’t be more effective from top down as in top down we are computing the fib of all no.'s again and again for each query
Whereas in memoisation we were storing the already calculated results.?
Do you mean that the cost of saving the space for functions in memoisation is more than computing the fibon. for all no.s again and again ?
Memoisation way and the top down approach confusion
@Ramitgoel I think you are confused. When we solve our problem with a recursive function and memoize the results,it is called top-down dynamic programming. So we do memoization in top down dp to avoid repetition of sub problems.
Memoization often starts at the top, defines itself recursively (assuming the work is already done), and caches results so duplicate sub-trees are not recomputed.
example: If you are calculating the Fibonacci sequence fib(100), you would just call this, and it would call fib(100)=fib(99)+fib(98), which would call fib(99)=fib(98)+fib(97), …etc…, which would call fib(2)=fib(1)+fib(0)=1+0=1. Then it would finally resolve fib(3)=fib(2)+fib(1), but it doesn’t need to recalculate fib(2), because we cached or memoized it.
Refer this article to check the difference between Top Down Dp using memoization and Bottom Up Dp using tabulation.
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.