Minimizing Coins (CSES 1634)

Problem Link: Minimizing Coins

Approach

Classic coin change. $dp[x]$ = minimum coins to make sum $x$. For each coin $c$, $dp[x] = \min(dp[x], dp[x-c] + 1)$.

Solution

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x; cin >> n >> x;
    vector<int> c(n);
    for (auto& v : c) cin >> v;
    vector<int> dp(x + 1, 1e9);
    dp[0] = 0;
    for (int i = 1; i <= x; i++)
        for (int coin : c)
            if (coin <= i) dp[i] = min(dp[i], dp[i - coin] + 1);
    cout << (dp[x] == 1e9 ? -1 : dp[x]);
}