Eliminating Recursion stack space

29 views Asked by At

When we convert a recursion to memoization we reduce time complexity but increase space complexity (eg: fibonacci series dp problem) but we can get rid of recursive stack space by tabulation which is the bottom up evaluation of subproblems.

But we need previous 2 consecutive terms for the evaluation of next term, refer this: https://www.baeldung.com/cs/fibonacci-top-down-vs-bottom-up-dynamic-programming enter image description here

If we needed terms which aren't consecutive for calculating a subproblem can bottom up approach be followed?

If we can't follow bottom up approach in these cases, can we conclude that every memoization(top-down) solution of any dynamic programming problem can't be converted to its tabulation solution(bottom-up)?

0

There are 0 answers