Coin change algorithm with dynamic programming

Question

I have problems with dynamic programming. I tried to solve a trivial coin change problem - CHANGE SAVING UVa Problem

I try to use the top-down principle with remembering, but I get 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 that I am doing wrong memorization or from top to bottom will not work in this case, and the bottom-up approach is the only option.

Answer 1

You do not need to call the Coin function for each test (each value of n), since m (the number of coin types) remains the same in all cases, so name it only once for the maximum value, which is 7489. Here, and then answer for all test files as dp [n] [4]. For a better understanding, see the code below.

 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; }