Coin Change Algorithm

 

Coin Change

coin[i]	i \ j	0	1	2	3	4	5	6
0	0	0	inf	Inf	Inf	Inf	Inf	inf
1	1	0	1	2	3	4	5	6
2	2	0	1	1	2	2	3	3
5	3	0	1	1	2	2	1	2

Fill up:

At first include 0 and sort the coins 0, 1, 2, 5….

          All values in first column 0

          All rest values in first row is inf

IF j < coin[i] : place upper value

ELSE : min (upper, 1 + (j – coin[i])th indexed column at 

  same row)

Trace Back:

Select last value

IF the value came from upper : move to upper

ELSE : include the coin to answer Then move to the cell 

which column index equals to sum - coin[i] in same row then sum -= coin[i];

Repeat