How to memoizes this recurrence for minimum coin problem?

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.

1 Like
   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.


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);
    }
};
1 Like
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.

1 Like

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.

1 Like

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:- https://www.hackerrank.com/challenges/coin-change/problem
So, our dp-matrix is filled :slight_smile:
Now! Lets create a new-dp1-matrix :slight_smile:
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 :slight_smile:
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); :slight_smile:

1 Like

Oops sorry I just added memo part.
Haven’t changed your code.