兑换零钱问题，当用户给定金币面额时，同时规定，只有一部分硬币零钱可供兑换。问怎样安排能够在兑换的时候所用的数量最少。
兑换零钱题目也是动态规划中比较典型的问题，通常可以用递归解决，不过递归复杂度较大，且重复值较多。所以可以利用逐层求解的方法。
此类题目在leekcode上也有，问题大致如下：
有以下类型的金币：
2 5 10 60
需要兑换的金额为130，问怎样兑换可使兑换的硬币最少。
以下为代码部分：
//主函数
public class test11 {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();//硬币的种类数
int s=in.nextInt();//总金额
int[]a=new int[n];//用来存放硬币金额
for(int i=0;i
//方法
static int dp(int[]a,int x){//a为硬币金额数组，x为金额数
int F;
int[]f=new int[x+1];//遍历金额
int[]s=new int[a.length];//临时标记数组
for(int i=1;i
运行结果如下：
