Is it possible to solve the coin denomination problem using a 1-D array?

Question

In an algorithm book it said that to solve the coin denomination problem via Dynamic Programming approach a 2-D array is needed:

Exercises 8.4 #9

Is it not possible to do this using a 1-D array.

I was thinking that maybe you could set the $C$ values in a 1-D array as: $C[0]=0$, $C[n]=1$ if $n$ is one of the denomination values and $C[n]= \infty$ if $n$ is less that the least denomination.

Otherwise set $C[n] = \min_{1 <= i <= \frac{n}{2}}{(C[i]+C[n-i])}$

What is wrong with my solution other than I won't be able to generate the actual solution because my goal is only to find the optimal number of coins for that $n$ value?

Answer 1

It is perfectly possible to solve the problem using a 1D array. Actually, you can even reconstruct the solution using just that 1D array. There are often multiple ways to solve a given problem, and in this case there's a neat time-memory tradeoff: in the 1D example you need $O(m)$ time to compute the value of one array slot, in the 2D example you only need $O(1)$ time but there are $O(nm)$ slots rather than just $O(n)$.