#include <stdio.h>





/* Coin denomination problem
 * Return the minimum number of coins in the set {C1,C2...Cn}
 * to sum up exactly X
 */


/* Recursive solution. Optimal but slow */
int CoinsRec( int *coins, int ncoins, int amount ) {

	int min = -1;
	int i;
	int tmp;

	for ( i=0; i < ncoins; i++) {

		if (amount - coins[i] > 0 ) {
			tmp = 1 + CoinsRec( coins, ncoins, amount - coins[i] );
			if (min == -1 || tmp < min) 
				min = tmp;
		} else if (amount - coins[i] == 0) {
			return 1;
		}

	}

	return min;
}



/* Dynamic Programming solution. Optimal and fast :) */
int CoinsDyn( int *coins, int ncoins, int amount ) {
	
	/* For simplicity, we just use an array from 0 to amount to
	 * store intermediate results. Could do with a hash table too
	 */
	int A[amount+1];

	int i,j;
	for (i=0; i < amount+1; i++)
		A[i] = -1;

	/* Trivial solutions */
	for (i=0; i < ncoins; i++)
		A[coins[i]] = 1;


	/* Calculate the rest */
	for (i =0; i <= amount; i++) {
		if (A[i] != -1) 
			continue;
		int min, tmp;

		min = -1;
		for (j=0; j < ncoins; j++) {
			if (i - coins[j] >= 0) {
				tmp = 1 + A[i - coins[j]];
				if (min == -1 || tmp < min)
					min = tmp;
				
			}
		}
		A[i] = min;
	}
	return A[amount];
}



int main( void ) {
	
	int coins[] = {1, 2, 5, 10};
	int ncoins = 4;
	int amt = 97;
	int res;

	/*
	printf( "Calculating Recursive Solution...\n" );
	res = CoinsRec( coins, ncoins, amt);
	printf( "Result: %d\n", res );
	*/

	printf( "Calculating Dynamic Programming Solution...\n" );
	res = CoinsDyn( coins, ncoins, amt);
	printf( "Result: %d\n", res );



}