题解 | #最小邮票数#

最小邮票数的思想是： 当前需要凑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;
    
}