Minimizing Coins

Solution by dudu — 100 pts

Code / Notes

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int INFINITO = 1000000000;

// Além de salvar valor (pra deixar mais rapido)
// Faltam algumas coisas:
//  - agora pode ficar negativo (OK!)
//  - CASO BASE! (zero)

vector<int> C;
vector<int> memo;
int minCoins(int falta) {
    if (falta == 0) {
        return 0;
    }
    if (memo[falta] != -1) {
        return memo[falta];
    }
    int ans = INFINITO;
    for (int i = 0; i < C.size(); i++) {
        int agora = falta - C[i];
        if (agora >= 0) {
            ans = min(ans, 1 + minCoins(agora));
        }
    }
    return memo[falta] = ans;
}

int main() {
    int N, S;
    cin >> N >> S;

    C.resize(N);
    for (auto &x : C) cin >> x;

    memo.resize(S+1, -1);

    int ans = minCoins(S);
    if (ans == INFINITO) cout << -1 << endl;
    else cout << ans << endl;
}

Last updated 1 month ago

« Back to problem