2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$
    – Raphael
    Apr 3, 2016 at 8:30

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.