最小邮票数

用动态规划，每次从大数开始更新。

#include <iostream>
#include<cstring>
#define INF 1005

using namespace std;

const int N = 21;
const int M = 101;

int stamp[N];
int dp[M];

int main(){
    int m, n;
    while(cin >> m){
         cin >> n;
        for(int i = 0; i < n; i++){
            cin >> stamp[i];
        }
        //memset(dp, INF , sizeof(dp));
        for(int i = 0;i <= m;i++){
            if(i==0){
                dp[i]=0;
            }
            else{
                dp[i] = INF;
            }
        }
        //扫描每一张邮票
        for(int i = 0; i < n; i++){
            //遍历每个值需要的张数
            for(int j = m; j >= stamp[i]; j--){
                //if(dp[j-stamp[i]]!=INT_MAX)dp[j]=(dp[j] < dp[j-stamp[i]]+1)? dp[j]: dp[j-stamp[i]]+1;
                if(dp[j-stamp[i]]!= INF){
                    dp[j] = min(dp[j], dp[j - stamp[i]] + 1);
                }
            }
        }
        if(dp[m] == INF){
            printf("0\n");
        }else{
            printf("%d\n", dp[m]);
        }

    }
}