-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathtop-down DP vs Bottom-up DP.txt
14 lines (9 loc) · 1.23 KB
/
top-down DP vs Bottom-up DP.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Memoization has the same order complexity as tabulation (if tabulation is order of n it will be too, maybe slower by a constant factor)
But memoization is not always slower, it really depends upon the problems, on how it is going to be as compared to tabulation.
It might be slower (often this is the case) and it can be faster too (this can happen too).
All that depends upon the number of sub-problems and how they are distibuted in the recurisve tree.
If all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor (No overhead for recursion and less overhead for maintaining table)
There are some problems for which the regular pattern of table accesses in the dynamic-programming algorithm can be exploited to reduce the time or space requirements even further
If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required.
Bonus-> Why bottom-up is called as the name goes ?
It is called bottom-up, because we start the solution from base case (initialize matrix using base case) and build the solution to the top (t[n][w] in this case).