LeetCode 518 Coin Change 2

LeetCode

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

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

Constraints:

1 <= coins.length <= 300 1 <= coins[i] <= 5000
All the values of coins are unique. 0 <= amount <= 5000

题目大意：

求兑换硬币的种数

解题思路：

类似于LeetCode 322 Coin Change，那题求最小个数，此题求总数，也是用DP。
递归式：

1	dp[i] = sum(dp[j]), i = j + coins[i]

LeetCode 377 Combination Sum IV 题目基本一样，唯一区别是结果元素有序，属于排列
LeetCode 518 Coin Change 2 题目基本一样，唯一区别是结果元素无序，属于组合

解题步骤：

递归5部曲

注意事项：

for循环顺序不能错，先coin再dp，否则会有重复计算，如dp[3] = 2 + 1和1 + 2. 字面上理解也是可以知道重复。但如果coin先的话，就只能用1的硬币，第二轮是只能用2的硬币，如此类推，显然不会重复，dp[3] = dp[2] + 1(只用硬币1), dp[1] + 2(只用硬币2)

Python代码：

# dp[i] = dp[j], i = j + coins[i]
def change(self, amount: int, coins: List[int]) -> int:
	dp = [0] * (amount + 1)
	dp[0] = 1
	for coin in coins:
		for i in range(len(dp)): # [0, 0]
			if i + coin <= amount:
				dp[i + coin] += dp[i]
	return dp[-1]

算法分析：

时间复杂度为O(n*amount)，空间复杂度O(amount)