Hey, i am trying to solve this problem
Here is my solution, I made a recursive algorithm and trying to implement memoization, but i couldn’t make it, please help
long coun=0,m_item=LONG_MAX;
map<long,long> mp;
long getWays(long n, vector<long> c,long index) {
if(mp[n]){
return mp[n];
}
if(n==0){
return 1;
} else if(n<m_item){
return 0;
}
long ways=0;
for(long i=index;i<c.size();i++){
if(c[i]<=n)
ways+=getWays(n-c[i],c,i);
}
//mp[n]=ways;
return ways;
}
Why are you passing index? You have an infinite amount of each coin. The map is not necessary, just use an array of size n+1. You should pass the coin vector by reference, otherwise it’s creating unneccesary copies.
1 Like
By passing index, i was trying to do this:
Suppose coins are 1,2,3
Then I first use [1,2,3]
then [2,3]
and [3]
That gives the correct answer without repetition, but time limit exceeds…
If i start from 0, then there is repetition like
for n=5
[1,2,2]
[2,2,1]//so by passing index i make sure that this doesn’t repeat!
And I already got how to do it with dynamic programming…
Thanks for your help 
long long getways(const int n, const vector<long> &c,const int idx){
if(dp[n][idx]!=-1){
return dp[n][idx];
}
long long ans=0;
for(int i=0;;i++){
if(n-i*c[idx]<0){
break;
}
ans+=getways(n-i*c[idx], c, idx-1);
}
return dp[n][idx]=ans;
}
long long getWays(int n, vector<long> c) {
for(int i=0;i<=50;i++){
dp[0][i]=1;
}
for(int i=0;i<=n;i++){
if(i%c[0]==0){
dp[i][0]=1;
}
else{
dp[i][0]=0;
}
}
return getways(n,c, c.size()-1);
}
Just memoise where dp[i][j] means the number of ways to make i cents only using the first j+1 coins.
1 Like
Simple One
long getWays(long n, vector<long> c) {
long ways[n+1]={0};
ways[0]=1;
for(long i=0;i<c.size();i++){
for(long j=0;j<=n;j++){
if(c[i]<=j){
ways[j] += ways[j-c[i]];
}
}
}
return ways[n];
}