Mahmud_Saikat's blog

Why memoization needs more states than tabulation?
By Mahmud_Saikat, history, 10 months ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Its_Saikat_19 (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Its_Saikat_19 (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the terminology "tabulation" an academic and standard term for "iterative" DP?

You can do DP in either two ways, recursion, and iteration (for loops) 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 for loops as they break the immutability rule. So iteration is done recursively and common helper functions like forEach, map, and filter are 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.

→ Reply