Coin Change

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5int main(){
    6    ios::sync_with_stdio(0);
    7    cin.tie(0);
    8    int x, n;
    9    cin >> x >> n;
    10    vector<int> coin;
    11    for(int i = 0; i < n; i++){
    12        int c;
    13        cin >> c;
    14        coin.push_back(c);
    15    }
    16    vector<int> dp(x + 1, 0x3f3f3f3f);
    17    dp[0] = 0;
    18    for(int i = 1; i < dp.size(); i++){
    19        for(int c : coin){
    20            if(c <= i){
    21                dp[i] = min(dp[i], dp[i - c] + 1);
    22            }
    23        }
    24    }
    25    cout << dp[x] << '\n';
    26    return 0;
    27}