最小邮票数的思想是: 当前需要凑j块钱, 选择了面额为a[i]的邮票,那么可以有两个选择 第一:仍然保持dp[j]张数量不变; 第二:选择面额为j-a[i]与面额为a[i]的邮票,其有票数为两者之和,即为dp[j-a[i]] + 1; 寻找最优解,即选择两者的最小值。 由动态规划的思想,从面值大的往面值小的遍历,既可以得到最后的答案。

#include<stdio.h>

int dp[100];

int main(){
    int m,n;
    while( scanf("%d", &m) != EOF){
        scanf("%d", &n); 
        int a[n];
        for(int i=0; i<n; i++){
            scanf("%d", &a[i]);
        }
        for(int i=0; i<100; i++){
            dp[i] = n+1;
        }
        
        dp[0] = 0;  dp[a[0]] = 1;
        
        for(int i=1; i<n; i++){
            for(int j=m; j>=a[i]; j--){
                dp[j] = fmin( dp[j], dp[j-a[i]] + 1);
            }
        }
        
        if(dp[m] <= n){
            printf("%d\n",dp[m]);
        }else{
            puts("0");
        }
    }
    return 0;
    
}