题解 | #最小邮票数# 容易理解的背包问题

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

using namespace std;

int main() {
   int m,n;
   while(cin>>m>>n){
        int *arr=(int *)malloc(sizeof(int)*(n+1));
        for(int i=1;i<=n;++i) cin>>arr[i];
        vector<vector<int>>dp(n+1,vector<int>(m+1,101));  //dp[i][j]表示前i个邮票构成j分最少邮票数，初始化为全101，表示无法构成
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){  
                if(arr[i]>j) dp[i][j]=dp[i-1][j]; //如果票的面值大于当前的j分，不选该票
                else if(arr[i]==j) dp[i][j]=1;  //若相当更改为1
                else {              //若选或者不选都达不到j分，则标记为无法构成
                    if(dp[i-1][j-arr[i]]==101 && dp[i-1][j]==101) dp[i][j]=101;
                    else dp[i][j]=min(dp[i-1][j-arr[i]]+1,dp[i-1][j]);
                } 
            }
        }
        if(dp[n][m]==101) cout<<0<<endl;
        else cout<<dp[n][m];
   }
}