#include <stdio.h>

#define N 50
#define CHANGESIZE 4

int changeSize;

// Sum upto 50
int table[N + 1][CHANGESIZE + 1];

// Returns the count of ways we can sum  S[0...m-1] coins to get sum n
int count( int S[], int m, int n )
{
    // If n is 0 then there is 1 solution (do not include any coin)
    if (n == 0)
        return 1;

    // If n is less than 0 then no solution exists
    if (n < 0)
        return 0;

    // If there are no coins and n is greater than 0, then no solution exist
    if (m <=0 && n >= 1)
        return 0;

    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

int getchange(int n, int denom)
{
    int next_denom = 0;

    switch(denom) {
	case 25:
	next_denom = 10;
	break;

	case 10:
	next_denom = 5;
	break;

	case 5:
	next_denom = 1;
	break;

	case 1:
	return 1;
    }

    int ways = 0;
    int i = 0;

    for (i = 0; i*denom <= n; i++) {
	ways += getchange(n - i*denom, next_denom);
    }

    return ways;
}

// Converted top down DP version of count()
int countDP(int S[], int m, int n)
{
    if (n == 0) {
	table[n][m] = 1;
	return table[n][m];
    }
    if (n < 0) {
	return 0;
    }

    if (m <=0 && n >= 1)
        return 0;

    if (n-S[m-1] < 0) {
	return 0;
    }

    if (table[n][m-1] == 0) {
	table[n][m-1] = countDP(S, m-1, n);
    }

    if (table[n-S[m-1]][m] == 0) {
	table[n-S[m-1]][m] = countDP(S, m, n-S[m-1]);
    }

    return (table[n][m-1] + table[n-S[m-1]][m]);
}

void inittable()
{
	int i = 0;
	int j = 0;
	
    for (i = 0; i < N + 1 ; i++) {
	for (j = 0; j < changeSize + 1; j++) {
	    table[i][j] = 0;
	}
    }

    return;
}

int main()
{
    int ways = 0;
    int sum = 0;
    int change[4] = {25, 10, 5, 1};
    changeSize = sizeof(change)/sizeof(change[0]);

    for (sum = 1; sum < 50; sum++) {
	printf("Sum %d\n", sum);
	printf("Count = %d\n", count(change, changeSize, sum));

	printf("GetChange = %d\n", getchange(sum, 25));

	ways = countDP(change, changeSize, sum);
	printf("CountDP = %d\n", ways);
	printf("============\n\n");

	inittable();
    }

    return 0;
}