674 - Coin Change

Problem link

It is a classical problem of Coin change problem.
In this problem test case number has no limit(>10^7). So, if you call recursion function for each test case it must get WA. To get ride off this problem you have to do pre-calculation and store answer in a array.

My Code is given below:

#include<bits/stdc++.h>
using namespace std;

int A[] = {1,5,10,25,50};
int table[7490];

void coin_change()
{
    memset(table,0,sizeof(table));

    table[0] = 1;

    for(int i = 0; i < 5; i++)
        for(int j = A[i]; j <= 7489; j++)
            table[j] += table[j-A[i]];
}

int main()
{
    int make;
    coin_change();
    while(cin>>make)
    {
        cout<<table[make]<<endl;
    }

    return 0;
}