Coin Change Algorithm with Dynamic Programming

Question

I am facing difficulty with Dynamic Programming. I was trying the trivial Coin Change problem- COIN CHANGE Problem UVa

I am trying to use top-down approach with memorization but I am getting TLE. Here is my code-

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

typedef vector <int > vi;
typedef vector <vi> vii;
const int maxn = 10000007;

int Set[maxn];
int Coin(int n,int m,vii & dp)
{   
    if(n==0)
        return 1;
    else if(n<0 || m<0)
        return 0;

    else if(dp[n][m]!=-1)
        return dp[n][m];
    else
    {
        dp[n][m]=Coin(n-Set[m],m,dp)+Coin(n,m-1,dp);

        return dp[n][m];
    }
}

int main()
{
    int n,m=5;
    Set[0]=50,Set[1]=25,Set[2]=10,Set[3]=5,Set[4]=1;
    while(scanf("%d",&n)!=EOF)
    {       
        vector <vector <int> > dp(n+1,vector<int> (m,-1));
        dp[0][0]=0;
        cout << Coin(n,m-1,dp) << endl;
    }
}

I want to know am I doing memorization wrong or top-down will not work in this case and bottom-up approach is the only option.

Answer 1

You do have not to call Coin function for every testcase(each value of n) as m(number of types of coins) remains same in all cases so call it only once for maximum value which is 7489 here. and then answer for all testcase as dp[n][4]. Please see the code below for better understanding.

n = 7489;
vector <vector <int> > dp(n+1,vector<int> (m,-1));
 dp[0][0]=0;
 Coin(n,m-1,dp);
while(scanf("%d",&n)!=EOF)
{       

    cout<<dp[n][4]<<endl;   
}