题解 | #最小邮票数#

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

int main() {
  int m, n;
  cin >> m >> n;
  vector<int> nums(n);
  for(int i=0; i<n; i++){
    cin >> nums[i];
  }
    vector<int> dp(m+1);    //在容量为j的情况下最少需要多少个
     for(int i=0; i<n; i++){
        for(int j=m; j>=nums[i]; j--){
              if(nums[i]==j)
                dp[j] = 1;
            else if(dp[j-nums[i]]!=0 && dp[j]==0)
                dp[j] = dp[j-nums[i]]+1;
            else if(dp[j-nums[i]]!=0 && dp[j]!=0)
                dp[j] = min(dp[j-nums[i]]+1,dp[j]);
        }
    }

    cout << dp[m] << endl;

}
// 64 位输出请用 printf("%lld")