My Seventy-fourth Page - 零钱兑换Ⅱ - By Nicolas

这篇page是针对leetcode上的518.零钱兑换Ⅱ所写的。小尼先简单的说明一下这道题的意思，就是给出一个整数数组coins表示不同面额的硬币，另外给出一个整数amount表示总金额，需要计算并返回可以凑成总金额的硬币组合数，吐过任何硬币组合都无法凑成，就直接返回0.

其实这道题就是一道典型的完全背包问题，在这里我们的不同价格的硬币就是可以不断地使用的，小尼在这里给出的解题的思路其实就是我们设置一个dp数组，然后我们不断地进行对应的加入。小尼接下来先给出动态规划五部曲：

1、确定dp[i]的含义：其实dp[i]就是当我们的背包容量为i时我们可以放入的最大种类，其实就是对应着我们这里的我们要求背包总额为i时我们可以放入物品的放入方法的最大种类。

2、确定递推公式：我们这里的递推公式就是：dp[j] += dp[j-coins[i]]其实就是我们我们将我们背包最大容量数减此时取的硬币数不断地进行累加，我们对每一个的累加都是对不断遍历取后面硬币提供前期元素。

3、dp数组如何进行初始化：其实这道题的初始化比较的简单，小尼之前就已经写过类似的题目，我们观察这个题目的递推的规律我们可以发现其实我们都是的种类数字都是一个一个累加上去的，所以我们第一个数据一定就是1，即dp[0] = 1

4、确定遍历顺序：我们的外层for循环遍历物品，内层for循环遍历背包

5、最后就是直接导出我们的递归的结果

小尼接下来给出解题的代码：

class Solution {
    public int change(int amount, int[] coins) {
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

小尼再这道动态规划题里面最开始有几个问题的，小尼一一说出我的疑问，希望小伙伴们也有跟我一样的疑惑，并且小尼最终找到了原因，小尼先说一说小尼的疑问，首先就是这里我举得并没有做一个“求和”的操作，就是小尼觉得这里好像并没有判断取出来的数加起来等于target的一个判断的操作啊，就是感觉莫名奇妙的就我们的个数的值就在不断地的增大，小尼这个时候就来做出一个解释，其实我们的判断的操作是在不断的进行着的，我们进行对应的操作就是dp[j] += dp[j-coin[i]]也就是说我们满足的是j-coins[i]也就是我们取出的硬币的值coins[i]加上j-coins[i]会等于我们j的值，所以其实所谓的判断的操作就是在这里进行的，如果不满足相加的和为j，我们的数值是不能被加的。

小尼的第二个疑问就是我们哪里体现了多次取物品的操作，其实小伙伴们可以手动的去写一写dp数组取出来的值，比如我举一个例子，我们在放coins[0]也就是价值为1的硬币的时候，我们不断地加入，我们首先是dp[1] = 1; 然后是dp[2] = dp[2] + dp[1] = 1；然后是dp[3] = dp[3] + dp[2] = 1,我们此时就可以观察此时数值的变化就是我们dp[3]其实就是在dp[2] 的基础上取多取了一次我们的coins，但是次数其实就是我们可以组成dp[2]的次数，包括后面的递归的操作思想的体现都是这样进行的。

希望小伙伴们可以得到帮助~~~