零钱兑换（力扣）JAVA_java零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入： 

coins = [1, 2, 5], amount = 11

输出： 

3 

解释：11 = 5 + 5 + 1
示例 2：

输入： 

coins = [2], amount = 3

输出： 

-1

示例 3：

输入： 

coins = [1], amount = 0

输出： 

0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

理解：本题的做法非常的多，可以用深度优先，广度优先，以及带备忘录的深度优先，以至于动态规划也可以解决本题。这些做法从左往右其效率也是逐渐变高。计算机计算一道题无非就是穷举，代码效率的高低关键是能否把穷举中重复的例子删掉，从而不断提升代码的质量。以下就是对代码不断优化的过程。

一，深度优先，从前往后记录+回溯。

import java.util.*; 
public class Main {
    public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int coins[] = new int[n];
    for(int i = 0;i < n;i++)
    coins[i] = sc.nextInt();
    int amount = sc.nextInt();
    Solution s = new Solution();
    s.changecoins(coins, amount);
    System.out.print(s.flag<0?s.flag:s.Number);
    }
}
class Solution {
int number;
int Number;
int flag;
int memo[];
Solution()
{
  number = -1;
  Number = Integer.MAX_VALUE;
  flag = -1;
  memo = new int[100];
}
public void changecoins(int a[], int amount)
{ 
  number++;
  if(amount == 0)
  {
	flag++;
	Number = Math.min(Number, number);  
	return;
  }
  int xx;
  for(int i = 0;i < a.length;i++)
  {
	xx = amount - a[i];
	if(xx >= 0)
    {
	  changecoins(a, xx);
	  number--;
	}
  }
}
}

1.此代码是我目前比较常用的穷举手法，每次遍历一种情况number数值会变大，为了避免影响其他可能的情况，所以每次遍历完其他可能后都会将number数值回溯 ，当然此种解法是不能通过力扣的（力扣里的函数基本上都要求返还数值）。于是修改后的代码如下。

二，深度优先，从运行末端往前，返还最小值。

import java.util.*; 
public class Main {
    public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int coins[] = new int[n];
    for(int i = 0;i < n;i++)
    coins[i] = sc.nextInt();
    int amount = sc.nextInt();
    Solution s = new Solution();
    System.out.println(s.coinChange(coins, amount)); 
    }
}
class Solution {
    public int coinChange(int[] coins, int amount) {
    if(amount == 0)
    return 0;
    if(amount < 0)
    return -1;//退出条件
    int res = Integer.MAX_VALUE;
    for(int coin : coins)
    {
      int number = coinChange(coins, amount - coin);
      if(number == -1)
      continue;
      res = Math.min(res, number + 1);
    }
    return res == Integer.MAX_VALUE?-1:res;
    }
}

2.此代码是优化后的代码，切合力扣题目要求，由于本代码是深度遍历，在每次遍历末端，都会通过比较，返还最小值，这样循序渐进，就返还本题的最小值。但遗憾的是力扣中测试点给的数据过于庞大，本题的穷举自然就超时了。所以这时我就把方向指向去重，以下是去重历程。

三，广度优先。

import java.util.*; 
public class Main {
    public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int coins[] = new int[n];
    for(int i = 0;i < n;i++)
    coins[i] = sc.nextInt();
    int amount = sc.nextInt();
    Solution s = new Solution();
    System.out.print(s.coinChange(coins, amount));
    }
}
class Solution {
	 public int coinChange(int[] coins, int amount) {
	        if(amount == 0)
	        return 0;
	        int cnt =0;
	        Queue <Integer> qu = new LinkedList<>();
	        HashSet<Integer> s1 = new HashSet<>();//去重复
	        qu.offer(amount);
	        while(!qu.isEmpty())
	        {
	         cnt++;
	         int temp =qu.size();
	         int num = 0;
	         for(int i = 0;i < temp;i++)
	         {
	        	int xx = qu.poll(); 
	        	for(int j = 0;j < coins.length;j++)
	        	{
	        	  num = xx - coins[j];
	        	  if(num == 0)
	        	   return cnt;
	        	  if(num >0 && !s1.contains(num))
	        	  {
	        		qu.offer(num);
	        		s1.add(num);
	        	  }
	        	}	 
	         }
	        }
	        return -1;
	 }
}

3.本身广度优先搜索，就类似于地毯式找一颗扫雷，找到雷就直接退出遍历，对于本题就是地毯式找到能让零钱数变为0的路径，遇到0就直接退出，这可以很好的省去搜索下方0所需要的时间，又由于本代码加入了HashSet来去重复，这就又让效率上了一个档次。用此代码提交是可以通过的，但效果却不是特别的理想，我想很大一部分原因在于使用HashSet查重过程中耗费了太多时间。

四，深度优先，加备忘录，从后往前返还最小值

import java.util.*; 
public class Main {
    public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int coins[] = new int[n];
    for(int i = 0;i < n;i++)
    coins[i] = sc.nextInt();
    int amount = sc.nextInt();
    Solution s = new Solution();
    System.out.println(s.coinChange(coins, amount)); 
    }
}
class Solution {
	int memo[];
	public int coinChange(int[]coins, int amount)
	{
	  memo = new int[amount+1];
	  Arrays.fill(memo, -666);
	  return coin(coins, amount);
	}
	
    public int coin(int[] coins, int amount) {
    if(amount == 0)
    return 0;
    if(amount < 0)
    return -1;//退出条件
    if(memo[amount] != -666)
     return memo[amount];
    int res = Integer.MAX_VALUE;
    for(int coin : coins)
    {
      int number = coin(coins, amount - coin);
      if(number == -1)
      continue;
      res = Math.min(res, number + 1);
    }
    memo[amount] = (res== Integer.MAX_VALUE)?-1:res;
    return memo[amount];
    }
}

4.为了进一步对代码进行优化，我在其中加入了备忘录，此备忘录的作用就是当此数据计算过后会存入备忘录中，当在此遇到此重复数据时，会提取备忘录中的相应结果，避免了再次计算，大大减少了重复。对此代码进行提交，效果时相当的不错，不过值得一提的是备忘录也是需要存储空间的，在判断备忘录中是否存有某个数据所对应的值时也是需要一内内时间，不过由于备忘录是数组的形式所以查找所需要的时间要远远小于HashSet的，这也是本代码比上一个代码效率要高的原因之一。如果要问本题还有没有进阶的空间的话，那就是下方动态规划的方法。

五，动态规划解法

import java.util.*; 
public class Main {
    public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int coins[] = new int[n];
    for(int i = 0;i < n;i++)
    coins[i] = sc.nextInt();
    int amount = sc.nextInt();
    Solution s = new Solution();
    System.out.println(s.coinChange(coins, amount)); 
    }
}
class Solution {
    public int coinChange(int[] coins, int amount) {
      int dp[] =new int[amount+1];
      Arrays.fill(dp, amount+1);
      dp[0] = 0;
      for(int i = 0;i < dp.length;i++)
      {
    	for(int coin:coins)
    	{
    	  if(i - coin < 0)
    	   continue;
    	  dp[i] = Math.min(dp[i], dp[i - coin]+1);
    	}
      }
      return dp[amount] == amount+1?-1:dp[amount];
    }
} 

5.所谓动态规划，我目前的理解就是利用，题目中的递推关系，将原问题，分解成子问题，小的子问题推到出一个大的子问题......,大的子问题再层层递推出原问题,整个过程循序渐进动态变化。真正实现内存与效率的双赢（但要是找到动态规划的递推关系可不是一件容易的事）。

以上五种解法在力扣中的运行情况，由上至下分别为：

 

 

这就是本题，我由穷举，到删重优化，到进阶到动态规划的历程。