LeetCode 322 Coin Change

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 fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

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

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

1 <= coins.length <= 12 1 <= coins[i] <= 2<sup>31</sup> - 1
* 0 <= amount <= 10<sup>4</sup>

题目大意：

求兑换硬币的最小个数

解题思路：

用数值->个数DP模板

注意事项：

1. amount为0时候，返回0，表示不用coin也能满足，属于合法情况, dp[0] = 0(第二步)
2. 返回值，若dp[-1]为初始值，表示无解，返回-1(第5步)
3. 实现中dp[i] = min(dp[i], dp[i - j] + 1), +1在min内而不是min外。
4. 此题内外循环顺序不重要，跟LeetCode 518 Coin Change 2有区别

Python代码：

def coinChange(self, coins: List[int], amount: int) -> int:
	coins.sort()
	dp = [float('inf')] * (amount + 1)
	dp[0] = 0
	for coin in coins:
		for i in range(len(dp)):
			if i + coin <= amount:
				dp[i + coin] = min(dp[i + coin], dp[i] + 1)
	return dp[-1] if dp[-1] < float('inf') else -1  # remember

算法分析：

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