Sir ye pass ni hora gfg mei.please help

#1

#include <bits/stdc++.h>
typedef int in;
#define int long long
using namespace std;
int dp[1000001];
int minCoin(int v,int n ,int * arr){

if(v==0){
    return dp[v]=0;
}
if(dp[v]!=-1){
    return dp[v];
}
int ans=INT_MAX;
int count =0;
for(int i=0;i<n;i++){
    if(v>=arr[i]){
        int subprob = minCoin(v-arr[i],n,arr)+1;
        ans = min(ans,subprob);   
    }
    else{
        count++;
    }
    
}
if(count==n){
    return dp[v]=-1;
}
else
return dp[v]=ans;

}
in main() {
//code
int t;
cin>>t;
while(t–){
memset(dp,-1,sizeof(dp));
int n,v;
cin>>v>>n;
int *arr= new int[n];
for(int i=0;i<n;i++){
int x;
cin>>arr[i];
//arr.push_back(x);
}

    cout<<minCoin(v,n,arr)<<endl;
    
}
return 0;

}

#2
#3

@kumarroyjayanta your code is not correct.
for eg if input is:-
1
10 1
3
where total sum=10 and coin is only ‘3’.
then it should give answer as 0 but your code is giving 2.

Its because for every (arr[i]<= v) you are breaking it into a sub problem and adding 1 to it which is not correct. The case will be considered right when using these coins you are able to reach v==0.

#4


sir what about this.?? This is not passing

#5

@kumarroyjayanta you are not required to try saving the dp[v] at every step.
dp[v] should be updated when all the combinations have been tried.
Also this count==n means that you have tried all the combinations, so dont update it with -1.

Also incase of dp[v] = INT_MAX, we have to print -1.

I have done the required changes in your code, please have a look at this.

Also mark this doubt as resolved after solving it.

#6

sir what will dp[v] = INT_MAX indicate

#7

It indicates that it is not possible to make this amount using the given denominations

#8

ohh right.got it. that would mean ans was never updated and remained INT_MAX.thank you…