Untitled

#include <iostream>
#include <climits>
#include <vector>

using namespace std;

int main() {
    int suma;
    cout << "Introduceti suma de bani: ";
    cin >> suma;

    vector<int> monezi = { 1, 5, 6, 9 }; // Monezile disponibile
    int n = monezi.size();
    vector<vector<int>> a(n, vector<int>(suma + 1, INT_MAX)); // Initializare tabel

    for (int i = 0; i < n; i++) {
        a[i][0] = 0; // Pentru suma 0 nu avem nevoie de nicio moneda
    }

    for (int j = 1; j <= suma; j++) {
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                a[i][j] = a[i - 1][j]; // Luam solutia precedenta
            }
            if (j >= monezi[i]) {
                a[i][j] = min(a[i][j], 1 + a[i][j - monezi[i]]); // Incercam sa adaugam monezi[i] la solutia precedenta
            }
        }
    }

    if (a[n - 1][suma] == INT_MAX) {
        cout << "Nu exista solutie!";
    }
    else {
        cout << "Numarul minim de monezi necesare: " << a[n - 1][suma];
    }

    return 0;
}