【DP】518. Coin Change 2

问题描述：

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

Note:
You can assume that:

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

解题思路：

这道题是找组合方案数，而不是排列数。因此，如果使用 【DP、BFS】322. Coin Change 这道题中的 BFS 方法，貌似不可行。

但是，可以使用动态规划的思想去解决。创建一个大小为 dp[1+amount] 的数组，其中 dp[j] 表示总额为 j 的组合方案数。最后，dp[-1] 就是答案。

关键是如何找到状态转移方程。因为是要找组合方案数，所以对于 (1 2)、(2 1) 这种的其实是一样的，所以我们的外层循环应该是 coin，即 for coin in coins（这样就避免出现排列问题）。那么，内层循环 j 就是用 当前的 coin 去更新这个 dp 数组中的方案数。

转移方程式可以想到：dp[j] = dp[j-coins[i]]，但是因为外层循环的每个 coins[i] 都可能更新这个 dp[j]，因此最终的转移方程式应该为：
dp[j] = ∑ dp[j-coins[i]]
表示总额为 j 时的方案数 = 总额为 j-coins[i] 的方案数的加和。∑ 次数等于外层循环次数。

记得初始化 dp[0] = 1，表示总额为 0 时方案数为 1。其他位置的 dp[j] 初始化为 0。

时间复杂度 O(c*n)，空间复杂度 O(n)，其中 c 为硬币种类数，n 为总额 amount。

Python3 实现：

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [1] + [0] * amount
        for coin in coins:
            for j in range(coin, amount+1):
                dp[j] += dp[j-coin]  # dp[j] 是所有 coins 累加的结果
        return dp[-1]

print(Solution().change([2,1], 3))  # 2 (111，12)

拓展延伸：

如果这道题是求不同的排列数呢？比如 （1 2）和 （2 1）是不同的情况。那么该怎么去做？

其实，这个问题是 Leetcode 的另一道题：
【377】给一个数组和一个目标，求合成目标的不同组合数，与顺序有关