UVa - 357 - Let Me Count The Ways

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int Coin[] = {1, 5, 10, 25, 50};
long long dp[7][30003];
long long N;

long long makeCoin(long long I, long long H){
    if(I >= 5){
        if(H == 0)return 1;
        else return 0;
    }
    if(dp[I][H] != -1)return dp[I][H];
    long long Way1 = 0, Way2 = 0;
    if(H-Coin[I] >= 0)Way1 = makeCoin(I, H-Coin[I]);
    Way2 = makeCoin(I+1, H);
    return dp[I][H] = Way1+Way2;
}

int main(){
    memset(dp, -1, sizeof(dp));
    while(cin >> N){
        long long ans = makeCoin(0, N);
        if(ans == 1)cout << "There is only 1 way to produce " << N << " cents change." << endl;
        else cout << "There are " << ans << " ways to produce " << N << " cents change." << endl;
    }
    return 0;
}