完全背包之零钱兑换I

        上次分享完完全背包问题的解决思路后，这次分享一道和完全背包有关的leetcode题。

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

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

        这道题和完全背包问题相同点就是硬币的数量是无限的，可以重复使用，不同的是完全背包问题是使得背包里面物品的价值最大，不一定要装满背包，这道题则是恰好装满背包，要求使用的物品数量最少。解决思路也是装与不装，不装则是dp[j]，装的话，背包容量就需要减去物品重量，此时加上的不再是物品的价值，而是物品的数量，仅装入一个物品，物品数加1，要求硬币数量最少，所以要取最小值。这里有一个需要强调的点，就是dp数组的初始化问题，对于这种要求恰好装满背包，求最值的问题，dp数组的初始化首元素一般都是0，其次其余元素就需要看要求的是最大值还是最小值，这里要求物品数量最少，所以其余元素初始化为整数最大值。在上一篇的完全背包问题时，遇到恰好装满背包，背包价值最大，这是dp首元素为0，其余元素则初始化为整数最小值。
        这里以上述示例说明代码的执行流程。这里钱币的面值即是物品的体积，也是物品的价值，面值有1，2和5，总金额为11，所以dp数组初始化为11。dp数组如下所示，dp[j]的含义是金额为j需要的最小硬币数量为dp[j]：

        之后遍历面值1，当背包容量j(总金额)为0时，不满足j >= coins[0]，不进入if，背包容量j(总金额)为1时，j = coins[0]，并且j - coins[0] = 0，可以装下，dp[1] = min(dp[j], dp[j - coins[i]] + 1) = dp[0] + 1 = 1。这里就很好的说明为什么dp[0]为什么要初始化为0，不初始化为0，对结果有影响，而且dp[1]要初始化为整数最大值，如果初始化为别的数，如0的话，这里得到的结果就不是1，而是0，所以其余dp元素要初始化为整数最大值。背包容量j(总金额)为2时，dp[2] = min(dp[2], dp[j - coins[i]] + 1) = dp[2 - coins[0]] + 1 = dp[1] + 1 = 1 + 1 = 2，dp[3] = dp[2] + 1 = 3，如此重复，遍历完面值1，dp数组如下：

        之后遍历面值2，当背包容量j(总金额)为0和1时，不满足j >= coins[1]，保持原值，当j等于2时，j = coins[1]，dp[2] = min(dp[2]，dp[j - coins[1]] + 1) = min(2, dp[0] + 1) = 1，用于dp是一维滚动数组，因此dp[2]的值是1，现在遍历面值2时，dp[2]为1，接着j = 3，dp[3] = min(3，dp[3 - 2] + 1) = dp[1] + 1 = 2，dp[4] = min(4, dp[4 - 2] + 1) = dp[2] + 1 = 1 + 1 = 2，此时的dp[2]为1，在j = 2时，修改了dp[2]的值。dp[5] = min(5, dp[5 - 2] + 1) = dp[3] + 1 = 3，dp[6] = 3，如此重复遍历，得到dp数组如下：

        之后遍历面值5，当当背包容量j(总金额)为0，1，2，3，4时，不满足j >= coins[1]，保持原值，j等于5，dp[5] = min(3, dp[5 - 5] + 1) = 1，dp[6] = min(3, dp[6 - 5] + 1) = 1 + 1 = 2，如此重复，得到dp数组如下，这里就不再展开说明，遍历完所有面值，返回dp[11]即为最终结果。