Leetcode 322 零钱兑换
题意理解：
给你一个整数数组
coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回
-1。你可以认为每种硬币的数量是无限的。
coins表示不同值得元素，有无限个，目标是使用元素凑出目标值最少需要多少个硬币。
这是一个完全背包问题，但不是一个纯背包问题。因为这里问的不是背包里物品的重量或价值，而是最少用多少个硬币。
解题思路：
根据题意，我们可以得到
dp[j]表示凑出j最少使用dp[j]个硬币
递推公式：dp[j]=min(dp[j-coins[i]],dp[j])
从组合数和排列数来看，无论是组合数还是排列数其最少硬币数都是一样的，所以双for循环的顺序是可以颠倒的，对结果无影响。
由于物体可以重复取用，所以对于背包的遍历选择正序遍历。
1.解题
public int coinChange(int[] coins, int amount) {int[] dp=new int[amount+1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0]=0;for(int i=0;i<coins.length;i++){//遍历硬币for(int j=1;j<=amount;j++){//遍历背包if(coins[i]<=j){if(Integer.compare(Integer.MAX_VALUE,dp[j-coins[i]])!=0)dp[j]= Math.min(dp[j-coins[i]]+1,dp[j]);}}}return Integer.compare(Integer.MAX_VALUE,dp[amount])==0?-1:dp[amount];}2.分析
时间复杂度：O(n^2)
空间复杂度：O(n)