Why memoization needs more states than tabulation?
Разница между en1 и en2, 196 символ(ов) изменены
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/result/8535002/↵

tabulation solution (accepted) : https://cses.fi/problemset/result/8535217/↵

And it is clear that memoization not only needs extra state here but also is impossible with the given constraints.
Because it needs a 2D dp array with n * x size, so I do not have any submission link for memoization.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Its_Saikat_19 2024-02-25 14:09:54 321
en3 Английский Its_Saikat_19 2024-02-25 14:04:27 54
en2 Английский Its_Saikat_19 2024-02-22 12:47:57 196
en1 Английский Its_Saikat_19 2024-02-22 12:39:52 618 Initial revision (published)