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/8535002task/1636/↵
↵
tabulation solution (accepted) : https://cses.fi/problemset/result/8535217aste/d2e2d0644e0a8603822f62/↵
↵
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.
↵
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/
↵
tabulation solution (accepted) : https://cses.fi/p
↵
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.
