Coin Change (dp)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const ll mx=1005;

int coin[]= {50,25,10,5,1};
int make,dp[mx][mx];

int coin_change(int i, int amount)
{
    if(i>=5)
    {
        if(amount==0)
            return 1;
        else
            return 0;
    }

    if(dp[i][amount]!=-1)
        return dp[i][amount];
    int ret1=0,ret2=0;

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

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

    /// for finding how many way ret1`+ret2;
    /// for say yes or no ret1 | ret2;
}

int main()
{
    memset(dp,-1,sizeof dp);
    while(cin>>make)
    {
        cout<<coin_change(0,make)<<endl;
    }

    return 0;
}