674 - Coin Change

Problem link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=615

Solution :

#include<bits/stdc++.h>

using namespace std;

int dp[6][7492];

int amnt[]= {50,25,10,5,1};

int coin(int i,int ammount)
{
    if(i>=5)
    {
        if(ammount==0) return 1;
        else return 0;

    }

    int ret1=0,ret2=0;

    if(dp[i][ammount]!=-1) return dp[i][ammount];

    if(ammount-amnt[i]>=0) ret1=coin(i,ammount-amnt[i]);
    ret2=coin(i+1,ammount);

    return dp[i][ammount]=ret1+ret2;

}

int main()
{
    int make;

    memset(dp,-1,sizeof(dp));

    while(scanf("%d",&make)==1)
    {
        cout<<coin(0,make)<<endl;
    }

}