stamps с яки коментари

#include <iostream>
#define MAXN 5000
#define INFINITY 999999
using namespace std;

int n, a[MAXN], solution[MAXN], s, minimum;
int main() {
    cin >> s >> n;

    for (int i = 0; i < n; i++) { //въвеждаме номиналите
        cin >> a[i];
    }

    for(int i = 1; i <= s; i++) {
        solution[i] = INFINITY; //маркираме всяко решение като начална стойност +безкрайност
    }

    solution[0] = 0; //markirame 0-то решение с 0, щот това е мн важно, за да бачка задачата!

    for (int i = 0; i < n; i++) { //за всеки номинал отбелязваме, че съответната сума се постига с 1 марка
        solution[a[i]] = 1;
    }

    for(int i = 2; i <= s; i++) { //за всека сума намираме кои са подсумите, през които може да сме минали за да стигнем нея
        for(int j = 0; j < n; j++) { //тия подсуми реално идват от номиналите
            if(i-a[j]>=0) { //тва е от значение, щото нямаме "отрицателни" подзадачи...
                solution[i] = min(solution[i], solution[i - a[j]] + 1); //всеки път гледаме кое е по-малко - досегашната стойност на solution[i] или решението на подзадачата + 1 (добавяме 1 щот нали като от подзадачата прескочим в новата задача добавяме още 1 марка към арсенала от марки :D)
            }
        }
    }

    cout << solution[s] << endl; //решението накрая разбира се е в solution[s]
    return 0;
}