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 (

`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.