力扣322-零钱兑换（Java详细题解）
题目链接：322. 零钱兑换 - 力扣（LeetCode）
前情提要：
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
最近刚学完背包，所以现在的题解都是以背包问题为基础再来写的。
如果大家不懂背包问题的话，建议可以去学一学01背包和完全背包。
如果大家感兴趣，我后期可以出一篇专门讲解背包问题。
dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。
这里下文统一使用一维dp数组。
题目思路:
该题与零钱兑换 II 有些区别，零钱兑换 II 是求将背包装满有多少种方法。
本题是求凑成总金额所要的最少硬币个数。
如果凑成功返回最少硬币个数，如果不能凑成功就返回-1。
这里可以把总金额抽象为一个容器，也就是作为背包，而硬币可以作为物品。
那么本题可以抽象为将背包装满所需的最少物品数量。
而硬币的数量是无限的，那么就可以当做一个完全背包问题。
那么我们直接开始动规五部曲。
1.确定dp数组和i下标的含义。
dp[j] 是指背包容量为j时，所能装物品的最少数量。
2.确定递推公式。
本题是要求能装物品的最少数量。
每个物品只有俩个状态，选和不选。
当这个物品不选时，dp数组就为dp[j]。因为它不选，所以背包容量不会减少,物品数量也不会变，所以就为dp[j]
当这个物品选的时候，dp数组为dp[j - coins[i] + 1]。因为选择了i这个物品，所以我们要知道选择i之前的背包容量所能装的最少物品数量，然后选择了这个物品，那我们的物品数量就会加1。
因为我们是要求装满后最少的物品数量，所以需要将这个物品选和不选的情况取一个最小值。
所以我们的递推公式就为：dp[j] = Math.min(dp[j],dp[j - coins[i] + 1]);
3.dp初始化。
本题的初始化有很大讲究。
dp[0] 是指当背包容量为0时，能凑成0的最少硬币个数。硬币最小就为1。所以dp[0] = 0;
之前我们求的都是最大值，所以将非0下标初始化为0，是为了防止初始化的值来覆盖递推出来的值。
本题是求最小值，如果我将非0下标也初始化为0，那么我初始化的0就会将我递推出来的最小值覆盖，最后得出来为0。
因为我递推的最小值不可能比0更小。
所以在这里我们要将非0下标初始化为一个不影响我递推公式的值（不可能被dp数组取到的值），这个值可以为Integer.MAX_VALUE。
因为我初始化为最大的数值，其他的数肯定小于等于它，当我递推出一个比它小的值时，就能覆盖这个最大值，不影响我递推的值。
其实这里还可以优化一下，将所有值初始化为 amount + 1。这个值比Integer.MAX_VALUE要小，可以节约内存空间。
为什么可以初始化为amount + 1呢？
因为我们是要用硬币凑成amount，硬币最小的就是1，假设我们只有一种硬币就为1，那当他凑成amount就要amount个硬币个数。这是最多的硬币个数情况。
所以这里我们初始化为amount + 1。就比最多的硬币个数还多一点，这样dp数组也不可能取到这个值，也就不影响我的递推公式的值。
说简单点。
要求最大值的时候，尽量初始化为更小的数。
要求最小值的时候，尽量初始化为更大的数。
4.确定dp的遍历顺序。
在完全背包问题中，如果先遍历物品再遍历背包就是求的物品的组合。
如果先遍历背包后遍历物品就是求的物品的排列。
该题是求凑成总金额的最少硬币个数。
举个例子。如果我的总金额为3，硬币个数为1和2。
那我凑成这个金额的硬币可以是{1,2}也可以是{2,1}。
这俩种情况最少硬币个数都为2。所以我物品的排列组合是不影响我dp数组的。
所以该题既可以先遍历物品也可以先遍历背包。
5.如果没有ac打印dp数组 利于debug。
最终代码：
class Solution {
public int coinChange(int[] coins, int amount) {
//该题就是求将背包装满后最少的物品个数,如果不能装满返回 - 1
int dp[] = new int [amount + 1];
//将dp数组初始化为一个不可能实现的最大值（amount + 1)
for(int i = 1;i < dp.length;i ++){
dp[i] = amount + 1;
}
dp[0] = 0;
//先遍历物品后遍历背包
for(int i = 0;i < coins.length;i ++){
//j 初始化为 coins[j] 是为了避免数组dp[j - coins[i]]越界
//代码层次上讲是避免越界 思路上讲就是你在选择该物品前，得先确定你的背包容量能够装下该物品
for(int j = coins[i]; j <= amount;j ++){
dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);
}
}
//如果最后该背包没有装满 就为 -1 能装就为dp[amount]
return dp[amount] != amount + 1 ? dp[amount] : -1;
}
}
这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。
我很乐意为你解答。那么我们下篇再见！