[Leetcode] 518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。 
题目数据保证结果符合 32 位带符号整数。

$$ $$

典型的背包问题，可以直接使用DP解决。并且因为coins可以重复使用，这里是一个完全背包问题。

现在我们可以遵循DP的路径解决这个问题，即，定义DP状态，寻找状态转移方程，填充DP表。

根据我们对背包问题的理解，我们定义DP[i]为对目标为i时的方法数量，那么我们自然而然的可以得出我们的状态转移方程为$ DP[i] = \sum_{coin}{DP[i – coin]} $。现在的问题就变成了：我们应该以怎样的顺序去填充我们的DP表。

从状态转移方程中我们可以看出应该使用两层循环。在一开始，我顺理成章的思考了下面的解决顺序，外层循环控制余额，内层循环控制coin。但是我发现这样循环会有一个很严重的问题，即我们会将两个组成相同但是顺序不同的解决方案重复计算，而这是我们在这道题目中不希望见到的。于是我们思考将内外层循环调转顺序。为什么可以这样来解决冗余的问题呢？冗余问题的核心原因是我们考虑了所有的组合可能性。但是如果我们按照coin的顺序来更新dp表，我们可以看到，我们事实上在外层循环只考虑了“仅通过某一coin值，从一处到达i处的方式”，而这一顺序是按照coin，不重复的考虑的。这样，事实上我们直接省略了多余的考虑。

The END。