What's wrong in the code

general
,
1

Problem
MY code is giving TLE even after using DP

#include <bits/stdc++.h>
using namespace std ;
vector<int> dp((1e7)+2,-1);
//<- Global variables->
int fun(int x,vector<int> &coins){
    if(x==0) return 0;
    if(dp[x]!=-1) return dp[x];
    int ans=INT_MAX;
    for(auto i: coins){
        if((x-i)>=0)
        ans=min(ans+0LL,(fun(x-i,coins)+1LL));
    }
    // if(ans==1e9) return -1;
    return dp[x]=ans;
}
//solve the problem for each testcase
void solve(){
	
    int n,x;
    cin>>n>>x;
    vector<int>  coins(n);   
    // input(coins);
    for(auto &i: coins){
        cin>>i;
    }
    int a=fun(x,coins);
    // cout<<dp[x];
    cout<<(a==INT_MAX?-1:a);
}

int main(){
    solve();
}

@luvk1412

2

Check the following update to your code.

Accepted

3

oh, thanks.
I am using a top-down approach while the problem wants me to use bottom up

4

Bro your code is O(n^2)
It is not just about what parameter you put in memorization but also the function inside the recursive function will contribute in complexity.

5

any suggestion for solving this using Top down

6

Make a dp on (x, max possible coin value). You might want to use hashmap.