Does this algorithm cover all cases for finding minimum coin change for a sum?

2
votes

I am trying to solve the minimum coin change problem. The question is: Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, .. , Cm} valued coins, what is the minimum number of coins to make the change?

My algorithm suggested is:

Starting with an array arr[1..V],where V is the value:

  1. For all the denominations,initialise arr[d]=1 as this is the base case. If the value == demoniation of a coin,only 1 coin is required and hence it is the least

  2. For all values from i : 1...V: compute the minimum no of coins required to make change for a value of 'i'. 2.1. This can be done by : For all j: 1....(i-1) arr[i]=min(arr[i],arr[j]+arr[i-j]);

  3. return arr[V];

Is this logic flawed or does it cover all cases? Most DP solutions have used a 2-D array and I don't understand why they would use O(n^2) memory space,if this exists and is correct. Thank u.

1
algorithmdynamic-programming

1 Answers

0
votes

How about cases whre some value V cant be obtained?

i.e. we have coins {5,6,7,8,9} and we cant make values 1,2,3,4, You should initialize all value != demoniation cells to infinity constant or something similar.

Now for the reason most people use O(n^2) memory:

This problem comes with various flavors, most common one being you can only use each coin once, in this case using state dp[i][j] - min coins that sum to j after considering first i coins seem to be easier to understand for most people even though this can also be done with O(n) memory (just looping backwards)