题解 | 最小邮票数

#include <iostream>
#include <algorithm>
#include <cstddef>
#include <vector>

int main() {
    std::size_t sum; // 要求凑成的邮票总值
    std::size_t stamp_num; // 邮票数量
    while (std::cin >> sum >> stamp_num) {
        // 输入所有邮票
        std::vector<std::size_t> stamps(stamp_num + 1); 
        for(std::size_t i = 1; i <= stamp_num; ++i) std::cin >> stamps[i];

        // 初始化dp数组
        std::vector<std::vector<std::size_t>> dp(stamp_num + 1, std::vector<std::size_t>(sum + 1, 101));
        for(std::size_t i = 0; i <= stamp_num; ++i) dp[i][0] = 0;

        for(std::size_t i = 1; i <= stamp_num; ++i){
            for(std::size_t j = stamps[i]; j <= sum; ++j){
                dp[i][j] = std::min(dp[i - 1][j], dp[i - 1][j - stamps[i]] + 1);
            }
        }

        // 输出结果即可
        if(dp[stamp_num][sum] == 101) std::cout << 0 << std::endl;
        else std::cout << dp[stamp_num][sum] << std::endl;
     }

}