Uncommenting the commented part will give wrong answer.
//vi dp(1000001,-1);
int f(int x,int cnt,const vi &v){
if(x<0)return INT_MAX;
if(x==0)return cnt;
//if(dp[x]!=-1)return dp[x];
int ans=INT_MAX;
for(const int &i:v){
ans=min(ans,f(x-i,cnt+1,v));
}
//dp[x]=ans;
return ans;
}
f(11,0,{1,2,5}) should give 3 (5+5+1), but with memo (using map/vector) it gives 7.
map<int,int> m;
int f(int x,int cnt,const vi &v){
if(x<0)return INT_MAX;
if(x==0)return cnt;
if(m.find(x)!=m.end())
return m.find(x)->second;
int ans=INT_MAX;
for(const int &i:v)
ans=min(ans,f(x-i,cnt+1,v));
m.insert({x,ans});
return ans;
}
This should work
Nope… Getting the same problem again.
f(11,0,{1,2,5}) should give 3, but with memo (using map/vector) gives 7.
https://leetcode.com/problems/coin-change/
Code after memo. Gives incorrect answer. (try it on leetcode:)
#define vi vector<int>
class Solution {
public:
map<int,int> m;
int f(int x,int cnt,const vi &v){
if(x<0)return INT_MAX;
if(x==0)return cnt;
if(m.find(x)!=m.end())return m[x];
int ans=INT_MAX;
for(const int &i:v)ans=min(ans,f(x-i,cnt+1,v));
m[x]=ans;
return ans;
}
int coinChange(vector<int>& coins, int amount) {
int ans=f(amount,0,coins);
return (ans==INT_MAX?-1:ans);
}
};
int f(int x, const vi &v){
if(x < 0) return (int) 2e9;
if(x == 0) return 0;
if (dp[x] != -1) return dp[x];
int ans = (int) 2e9;
for(const int &i : v) {
ans = min(ans, 1 + f(x - i, v));
}
return dp[x] = ans;
}
The problem is the extra cnt variable. This implementation should be fine.
Yes this works, Can you explain why ‘cnt’ variable was not working?
if (x == 0) return cnt;. You return cnt, which can be > 0, for some cases. For x = 0, you always need 0 coins.
Still kind of confused… It was giving Right answer without memo.
And what if x is becoming zero like this: for eg: 5-> 5- 2->3 -3, ie (2,3 coin required for 5) for this I have to increment cnt so the answer is 2.
This is my solution.
First of all, write the basic solution for this:- The Coin Change Problem | HackerRank
So, our dp-matrix is filled 
Now! Lets create a new-dp1-matrix
Whenever; dp[i][j]=1;
dp1[i][j]=minimum number of coins need to reach ‘j’ (calculate this value manually as it is trivial)
Now, when dp[i][j]!=1;
dp1[i][j]=min(dp1[i-1][j], 1+dp1[i][j-x1]) ;
where ‘x1’ is the weight of the ith-item
Explanation;
5th coin=20 dollars;
say we have to reach 100 dollars using any of the first 5-coins ; we know that the minimum number of coins required to reach 100 dollars using the first 4-coins is ‘x’ ; so answer can be simply ‘x’ if we don’t care about the 5th coin ; lets care about the 5th coin in other case; so if we care about it; then; we know the minimum number of coins required to reach 80 dollars using any of the first 5-coins is ‘y’ ; so if we include the 5th coin one more time ; then y=dp1[i][j-20dollars] ; and dp1[i][j]=min(x,y);
Oops sorry I just added memo part.
Haven’t changed your code.