Why memoization needs more states than tabulation?

Revision en4, by Mahmud_Saikat, 2024-02-25 14:09:54

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.

Tags dp problem, memoization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Mahmud_Saikat 2024-02-25 14:09:54 321
en3 English Mahmud_Saikat 2024-02-25 14:04:27 54
en2 English Mahmud_Saikat 2024-02-22 12:47:57 196
en1 English Mahmud_Saikat 2024-02-22 12:39:52 618 Initial revision (published)