Menu
There are many problems that can be solved using Dynamic programming e.g. Longest increasing subsequence. This problem can be solved by using 2 approaches
My question is which is better approach in terms of time and space complexity?
261
Is tabulation always better than memoization? If all subproblems need to be solved in the given problem, tabulation mostly outperforms memoization since it has no overhead for recursion. The tabulation technique can use a preallocated array instead of a hash map.
Memoization is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs (as with the Fibonacci problem, above).
In Memoization, you store the expensive function calls in a cache and call back from there if exist when needed again. This is a top-down approach, and it has extensive recursive calls. In Dynamic Programming (Dynamic Tables), you break the complex problem into smaller problems and solve each of the problems once.
Tabulation is an approach where you solve a dynamic programming problem by first filling up a table, and then compute the solution to the original problem based on the results in this table.
Short answer: it depends on the problem!
Memoization usually requires more code and is less straightforward, but has computational advantages in some problems, mainly those which you do not need to compute all the values for the whole matrix to reach the answer.
Tabulation is more straightforward, but may compute unnecessary values. If you do need to compute all the values, this method is usually faster, though, because of the smaller overhead.
79
Asymptotically a dynamic programming implementation that is top down is the same as going bottom up, assuming you're using the same recurrence relation. However, bottom up is generally more efficient because of the overhead of recursion which is used in memoization.
35
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
