问题描述：
有n种币值的货币，收银员要找total的零钱，问找到的最小张数的零钱是多少。例如找13元，币值为5,2,1，最小张数为4张，为5*2+2+1。
输入：
第一行输入一个整数n，表示n种币值的货币。
再输入具体币值。
最后输入要找零钱。
输出：
输出一行，就是所找零钱张数的最小值。
样例输入：
3
5 2 1
13
样例输出：
4
源代码:
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int INF=100000;
int main()
{
int i,n,temp,total,number;
printf("请输入货币种类共多少个：\n");
scanf("%d",&n);
int value[n]; //存取每个纸币币值
int num[n]; //存取每个纸币数量
printf("请输入每种货币的币值，最小币值为1，保证有解：\n");
for(int i=0;i<n;i++){
scanf("%d",&temp);
value[i]=temp;
}
printf("请输入需要找零总和：");
scanf("%d",&total);
int d[total+1]; //存取每个找零值所需要最小的纸币张数
d[0]=0;
for(int i=1;i<=total;i++){
d[i]=INF; //一定要附初值，之前认为反正挺大没关系，最后发现也可能初值很小，有影响
for(int j=0;j<n;j++){
if(i>=value[j]){ //边界值一定要注意
d[i]=min(d[i],d[i-value[j]]+1);
}
}
}
printf("以下为找零最少纸币数：%d\n",d[total]);
return 0;
}
易错点总结
1.判断条件时i>=value[j]，一定不能忘了=号。=号表示刚好可以找完。一定要关注边界值。
2.数组一定要附初值，不然可能大可能小，让人摸不着头脑。
3.虽然得出了最小张数，但是路径如何记录是个问题？
参考文章
下面两个方法都是从动态规划来解决的，但是思路不太相同，可以借鉴
参考方法1 状态迁移点在求前几个状态
参考方法2 状态迁移点在最后一个货币
