零钱兑换问题

type

status

date

slug

summary

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

这道题是完全背包的变形题。在完全背包问题中，我们的要求是给定物品（无限制）的重量和价值，在不超过容量的情况下，获取最大价值。

而本题的题意翻译成完全背包问题，是给定物品（无限制）的重量，在恰好容量用完的情况下，所装的物品数量最少。

因此，在套用完全背包问题模板的时候，需要做一些调整。

恰好用完的代码表示：首先题意是目标是最少，我们需要将 dp 数组的初始值都设置为 INT_MAX/2 （防止溢出），并将 dp[0][0] 设置为 0。只有从 dp[0][0] 出发，才是正确的。原因是在普通的完全背包问题中，我们可以从 dp[0][j] 的出发，也就是最后背包会空 j 个容量。

这里直接套用模板了。这里可以对比一下完全背包问题和 0-1 背包问题的状态转移方程。

完全背包方程： f[i][j]=max(f[i - 1][j], f[i][j - v[i]] + w[i] ──这里将原始背包问题优化后的结果，从优化到后的结果。

0-1 背包方程：f[i][j]=max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])

当然，我们也可以使用滚动数组，来优化这个问题。完全背包使用滚动数组不用从后面遍历，可以直接从前往后遍历。

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

本题与上一题类似，这题是求方案数。我们知道在背包问题中，求解的问题无外乎三种情况：最大值、最小值、方案数。

最大值与最小值一般是通过比较得到最值的答案；方法数一般是通过加和来获得最终答案，也就是当前方案上数是之前方案上的组合。

在本题中，我们有不选、选 1 个、选 2 个、选 3 个等等的方案数相加。在代码中的表示通过循环求和来实现的，也就是 dp[i + 1][j] = dp[i + 1][j] + dp[i][j - k * coins[i]] 。

然后，这里还有个非常非常重要的点，就是最外两层循环遍历的顺序，是先遍历物品还是先遍历背包。结论是：先遍历背包后遍历物品是排列数；先遍历物品再遍历背包是组合数。

解释一下：

就是先遍历物品的话，是不是物品 1 将所有的背包容量遍历完后，再开始物品 2 遍历所有背包容量。是不是最后只会是 1、2、3、4 这种情况，而组合数是可以重复的。即 1、2、3、4 与 4、3、1、2 是一样的。

而先遍历背包容量的话，是当前容量所有物品都会遍历一遍，那就会出现。再遍历下一个背包容量的时候，也还是所有物品都会遍历一遍。因此，可能会出现 2、1 和 1、2 的情况。

还有求解方案数使用无符号数即 unsigned

同理，我们将这个三重循环的问题，使用完全背包中的优化手段，进行优化。

使用 t 代替 coins[i]

dp[i + 1][j] = dp[i][j] + dp[i][j - t]+ dp[i][j - 2 * t] + dp[i][j - t]+ dp[i][j - 3 * t];

dp[i + 1][j - t] = dp[i][j - t]+ dp[i][j - 2 * t] + dp[i][j - t]+ dp[i][j - 3 * t];

因此，dp[i + 1][j] = dp[i][j] + dp[i + 1][j - t] ，则有

同理，我们可以进行空间优化。我们发现不管我们是否操作，都有 dp[i + 1][j] = dp[i][j]; ，因此完全可以使用一维数组来表示，即 dp[j] = dp[j]; ，很合理吧。