My Seventy-seventh Page - 零钱兑换 - By Nicolas

这篇page是针对leetcode上的322.零钱兑换所写的。小尼先简单的说明一下这道题的意思，给出一个整数数组coins，表示不同面额的硬币，以及一个整数amount，表示总金额。需要计算并且返回可以凑成总金额所需的最少的硬币个数，如果凑不出来，就直接返回-1.

其实这道题就是一道典型的完全背包问题，因为我们的硬币的金额可以多次使用，并且我们这里给出需要达到的金额数就是对应我们完全背包里面的背包的容量。接下来，小尼说明一下这道题的金额的解法：

1、确定dp数组以及下标的含义：dp[j]就是表示凑足总额为j所需钱币的最小个数

2、确定递推公式：得到dp[j]，就只有一个来源，dp[j - coins[i]]，我们所取的递推公式就是：

dp[j] = min(dp[j - coins[i]] +1, dp[j])

3、dp数组如何初始化：我们应该知道凑足总金额为0所需钱币的个数一定是0，那么我们可以得出dp[0]  = 0

4、确定遍历顺序：其实因为此题球的是钱币的最小的个数，所以遍历的顺序就不想完全背包问题那么写死，也就是说此题并不强调是排列还是组合，所以本题小尼采取的就是外层for遍历物品，内存for遍历背包

5、最后就是我们需要导出dp数组

接下来小尼拉一下这道题的解题的代码：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        for(int j = 0; j < dp.length; j++){
            dp[j] = max;
        }
        dp[0] = 0;
        for(int i = 0; i < coins.length; i++){
            for(int j = coins[i]; j <= amount; j++){
                if(dp[j - coins[i]] != max){
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
}

小尼在这道题一开始其实是充满了疑惑，怎么感觉这道题跟0-1背包的解法和相似遍历条件与0-1背包的写法及其形似，但是小尼一定需要说明一点，在这里我们的内层for循环是从coins[i]开始进行的，而在0-1背包中内层的for循环确实从tatget开始进行的，这里也就是为什么0-1背包问题里面的物品只使用了一次，而这里面的物品确实多次使用，其实就是我们这里面的物品是在不断的依靠前面本层上一次dp数组的放入的数目进行对应的叠加的，但是我们0-1背包里面的数据只是根据我们上一层循环里面的数据进行叠加。

希望上面的代码可以帮助到小伙伴们~~~