题解 | #最小邮票数#

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

using namespace std;
int main() {
    int m, n;
    while (cin >> m >> n) {
        vector<int> stamps(n + 1, 0);
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 20));
        for (int i = 1; i <= n; i ++)
            cin >> stamps[i];
        dp[0][0] = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 0; j <= m; j ++) {//前i张邮票总和为j的最小邮票数
                if (j < stamps[i]) {
                    dp[i][j] = dp[i - 1][j];//避免出现j - stamps[i]小于0
                    continue;
                } else {
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - stamps[i]] + 1);//要不要选第i张邮票，试了才知道
                }
            }
        }

        if (dp[n][m] == 20)
            cout << 0 << endl;
        else
            cout << dp[n][m] << endl;
    }
    return 0;
}