题解 | 最小邮票数

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int M, N;
    while (cin >> M) {
        cin >> N;
        vector<int> stamps(N);
        for (int i = 0; i < N; ++i) {
            cin >> stamps[i];
        }

        // 初始化dp数组，dp[i]表示凑成总值i所需的最少邮票张数
        vector<int> dp(M + 1, INT_MAX);
        dp[0] = 0; // 凑成总值0不需要任何邮票

        // 动态规划填表
        for (int i = 0; i < N; ++i) {
            for (int j = M; j >= stamps[i]; --j) {
                if (dp[j - stamps[i]] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - stamps[i]] + 1);
                }
            }
        }

        // 输出结果
        if (dp[M] == INT_MAX) {
            cout << 0 << endl; // 无法凑成总值M
        } else {
            cout << dp[M] << endl; // 输出最少邮票张数
        }
    }
    return 0;
}