CSES – Minimizing Coins

#include<bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
int dp[1000005];
signed main(){
    int n,x; cin>>n>>x;
    vector<int> v;
    for(int i=0;i<n;i++){
        int a;cin>>a;
        v.push_back(a);
    }
    for(int i=1;i<=x;i++) dp[i] = 1e18;
    dp[0] = 0;
    for(int j=0;j<n;j++){
        for(int i=1;i<=x;i++){
            if(i-v[j] >= 0){
                dp[i] = min(dp[i], dp[i-v[j]] + 1);
            }
        }
    }
    if(dp[x] == 1e18) cout<<-1<<"\n";
    else cout<<dp[x]<<"\n";
    return 0;
}