Is there any case where memoization approach requires more states than tabulation?
I have heard that tabulation and memoization only differs by some memory efficiency and time efficiency.
But now I am facing a problem where the tabulation solution only needs a state, "amount". I tried to implement it using memoization but there I must keep track of the "index", otherwise it gives wrong answer.
problem link: https://cses.fi/problemset/task/1636/
tabulation solution (accepted) with 1D dp : https://cses.fi/paste/d2e2d0644e0a8603822f62/
tabulation solution (accepted) with 2D dp : https://cses.fi/paste/d40aa6fee8c71199825f90/
memoization solution (TLE) with 2D dp : https://cses.fi/paste/972af1e5f43728b8825fa2/
memoization solution for this problem with 1D dp seems like does no exist.
Auto comment: topic has been updated by Its_Saikat_19 (previous revision, new revision, compare).
Auto comment: topic has been updated by Its_Saikat_19 (previous revision, new revision, compare).
Is the terminology "tabulation" an academic and standard term for "iterative" DP?
You can do DP in either two ways, recursion, and iteration (
forloops) which you call tabulation. I consider both ways as memoization.I've recently learnt basic concepts in the functional programming paradigm. It's not correct to use
forloops as they break the immutability rule. So iteration is done recursively and common helper functions likeforEach,map, andfilterare used.So I believe that every algorithm that uses loops can be implemented with recursion.
Regarding the problem you mentioned: It is all about the order of solving the sub-problems.