#include <stdio.h>//需要更改coins数组和size代表的个数
#include <stdlib.h>
int coinChange(int*,int);
int min(int,int);
int main () {
int amount=0;
int coins[3]={1,2,5};
scanf("%d",&amount);
printf("%d",coinChange(coins,amount));
return 0;
}
int coinChange(int *coins, int amount){
int i,j;
int MAX=amount+1;
int *dp=(int*)malloc(MAX*sizeof(int));
int size=3;
for(i=0;i<=amount;i++){
dp[i]=MAX;
}
dp[0]=0;
for(i=1;i<=amount;i++){
for(j=0;j<size;j++){
if(coins[j]<=i){
dp[i]=min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount] > amount ? -1:dp[amount];
}
int min(int a, int b){
if(a<=b)
return a;
else
return b;
}