有多个不同面值的硬币，任意找，输入金额S，输出最少硬币数。
列如：有1,3,5三种面值的硬币，我有9元钱，能兑换的硬币数最少是多少枚？5+3+1=9，最少兑换三枚。
0元兑换0个，
1元兑换1个，
2元兑换2个，在1元的基础上加一个，
3元兑换1个，
4元兑换2个，4-3=1元，在3元的基础上加一个，
依次类推，所以提炼出动态转移方程;Min[i]=min(Min[i],Min[i-face[j]]+1),1<=i<=s,Min[i]保存i元兑换最少硬币数，face[j]表示硬币面值，初始化时将Min[i]初始化一个较大的数,Min[0]=0。
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 const int inf=0x3f3f3f3f; 5 const int maxn=1e3; 6 int Min[maxn]; 7 int face[3]={1,3,5}; 8 int main() 9 { 10 int s; 11 while(cin>>s) 12 { 13 for(int i=1;i<=s;i++) 14 { 15 Min[i]=inf;//初始化最大值；Min[0]还是为0； 16 } 17 for(int i=1;i<=s;i++) 18 { 19 for(int j=0;j<3;j++) 20 { 21 if(face[j]<=i) 22 Min[i]=min(Min[i],Min[i-face[j]]+1); 23 } 24 } 25 cout<<Min[s]<<endl; 26 } 27 return 0; 28 } 29
原文：https://www.cnblogs.com/yzlzm/p/12606498.html