Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
987 B
0
Indexable
Never
#include <vector> 
/*
int drivemem(vector<int> &num,int x,vector<int> &dp){ //dp[i] means min no of coins needed to make target i
    if(x==0) return 0;
    if(x<0) return INT_MAX;
    if(dp[x]!=-1) return dp[x];

    int mini=INT_MAX;
    for(int i=0;i<num.size();i++){
        int ans=drivemem(num,x-num[i],dp);
        if(ans!=INT_MAX) mini=min(1+ans,mini);    
    }
    dp[x]=mini;
    return mini;
}
int minimumElements(vector<int> &num, int x)
{
    vector<int> dp(x+1,-1);
    int ans=drivemem(num,x,dp);
    if(ans==INT_MAX) return -1;
     return ans;

}  */

int minimumElements(vector<int> &num, int x){ //tabulation
    vector<int> dp(x+1,INT_MAX);
    dp[0]=0;

    for(int i=1;i<=x;i++){
        for(int j=0;j<num.size();j++){

            if(i-num[j]>=0 && dp[i-num[j]] !=INT_MAX){
                dp[i]=min(dp[i],1+dp[i-num[j]]);
            }
        }

    }
    if(dp[x]!=INT_MAX) return dp[x];
    else return -1;
}