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