scala - Solve Coin Change Problems with both functional programming and tail recursion? -

i know how solve coin change problem both imperative programming , dp.

i know how solve coin change problem both fp , non-tail-recursion. compute same problem multiple times, lead inefficiency.

i know how compute fibonacci number both fp , dp/tail-recursion. lots of articles use example explain "fp can combined dp" , "recursion can efficient loop".

but don't know how solve coin change problem both fp , dp/tail-recursion.

i think it's strange articles on imperative programming mention inefficiency of computing same problem multiple times on coin change problem, while on fp omit it.

in more general sense, wonder whether fp powerful enough solve such kind of "two dimensional" problem, while fibonacci "one dimensional" problem. can me?

coin change problem:

given value n, if want make change n cents, , have infinite supply of each of s = { s1, s2, .. , sm} valued coins, how many ways can make change? order of coins doesn’t matter.

for example, n = 4 , s = {1,2,3}, there 4 solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. output should 4. n = 10 , s = {2, 5, 3, 6}, there 5 solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} , {5,5}. output should 5.

i meet problem while i'm learning scala, use scala demonstrate code if it's possible. lisp good. know little haskell.