DP problem - Coin Change

coin_change.c

/*
 * dp problem - coin change
 * change[n]: number of ways to make change of n with coin_set given
 *
 * example
 * with coin set {1,5,10,25,50}
 * There are 2050869227 ways to make change of 7400
 */
#include <stdio.h>
#include <string.h>

#define CHANGE_MAX 7490
#define COIN_SET 5

const int coin[COIN_SET] = {1,5,10,25,50};
int change[CHANGE_MAX+1];

void set_change_table()
{
	int i, j;
	memset(change,0,sizeof(change));
	change[0] = 1;

	/* dp bottom-up set */
	for(i=0;i<COIN_SET;i++){
		for(j=coin[i];j<=CHANGE_MAX;j++)
			change[j] += change[j-coin[i]] ;
	}
}

int main()
{
	set_change_table();
	int i, n = 7400;

	puts("coin set:");
	for(i=0;i<COIN_SET;i++){
		if(i)	putchar(' ');
		printf("%d", coin[i]);
	}
	putchar('\n');

	printf("There are %d method to make change of %d\n", change[n], n);
	return 0;
}