## Description

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

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


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

## Solutions

使用最小的零钱个数完成找钱任务。

### 0. Brute Force

DFS 暴力搜索。

# 1. Brute Force
# Time: O(S^n)
# Space: O(n)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if not coins or amount < 0:
return 0
return self.brute_force(coins, 0, amount)

def brute_force(self, coins, idx, amount):
if amount == 0:
return 0

if idx < len(coins) and amount > 0:
max_try = amount // coins[idx]
min_coins = float('inf')
for i in range(max_try+1):
if i * coins[idx] <= amount:
res = self.brute_force(coins, idx + 1, amount - i * coins[idx])
if res != -1:
min_coins = min(min_coins, res + i)
return min_coins if min_coins != float('inf') else -1
return -1
# Time Limit Exceeded
# 32/182 cases passed (N/A)


### 1. 记忆化递归

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if not coins or amount < 0:
return 0
memo = [[0 for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
return self.brute_force(coins, memo, 0, amount)

def brute_force(self, coins, memo, idx, amount):
if amount == 0:
return 0

if idx < len(coins) and amount > 0:
max_try = amount // coins[idx]
min_coins = float('inf')
for i in range(max_try+1):
if i * coins[idx] <= amount:
memo_val = memo[idx+1][amount - i * coins[idx]]
if memo_val != 0:
res = memo_val
else:
res = self.brute_force(coins, memo, idx + 1, amount - i * coins[idx])
if res != -1:
min_coins = min(min_coins, res + i)
return min_coins if min_coins != float('inf') else -1
return -1
# Time Limit Exceeded
# 32/182 cases passed (N/A)

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if not coins or amount < 0:
return 0
memo = [float('inf') for _ in range(amount + 1)]
return self.brute_force(coins, memo, 0, amount)

def brute_force(self, coins, memo, idx, amount):
if amount == 0:
return 0
if memo[amount] != float('inf'):
return memo[amount]
if idx < len(coins) and amount > 0:
max_try = amount // coins[idx]
# min_coins = float('inf')
for i in range(max_try + 1):
if i * coins[idx] <= amount:
res = self.brute_force(coins, memo, idx + 1, amount - i * coins[idx])
if res != -1:
memo[amount] = min(memo[amount], res + i)
return memo[amount] if memo[amount] != float('inf') else -1
return -1
# Time Limit Exceeded
# 32/182 cases passed (N/A)


Top-down 的形式过了：

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if not coins or amount < 0:
return 0
memo = [0 for _ in range(amount + 1)]
return self.brute_force(coins, memo, amount)

def brute_force(self, coins, memo, amount):
if amount < 0:
return -1
if amount == 0:
return 0
if memo[amount] != 0:
return memo[amount]
min_coins = float('inf')
for coin in coins:
res = self.brute_force(coins, memo, amount - coin)
if res >= 0:
min_coins = min(min_coins, res + 1)
memo[amount] = min_coins if min_coins != float('inf') else -1
return memo[amount]
# 182/182 cases passed (2100 ms)
# Your runtime beats 8.85 % of python3 submissions
# Your memory usage beats 25 % of python3 submissions (15.2 MB)


### 2. DP

dp[i] 表示拼到金额为 i 所用的最少纸币张数，初始化所有的只都是很大的数（可以用 amount 的数值代替）。

$dp[i] = min(dp[i], dp[i-coin_i] + 1)$
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if not coins or amount < 0:
return 0
memo = [float('inf') for _ in range(amount + 1)]
memo[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
memo[i] = min(memo[i], memo[i-coin] + 1)
return memo[amount] if memo[amount] != float('inf') else -1
# 182/182 cases passed (1368 ms)
# Your runtime beats 57.1 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13 MB)


### 3. DFS + Greedy

class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
coins.sort(reverse=True)
self.res = float('inf')

def dfs(s, amount, count):

# reach last coin
if amount == 0:
self.res = count
return
if s == len(coins):
return

coin = coins[s]
for k in range(amount // coin, -1, -1):
if count + k < self.res:
# pruning, only search if new ans is less than current ans
dfs(s + 1, amount - k * coin, count + k)
dfs(0, amount, 0)
if self.res < float('inf'):
return self.res
else:
return -1

# Time Limit Exceeded


反而时间上过不了。

还有一种没看懂的……

class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
coins.sort(reverse = True)
lenc, self.res = len(coins), 2**31-1

def dfs(pt, rem, count):
if not rem:
self.res = min(self.res, count)
for i in range(pt, lenc):
if coins[i] <= rem < coins[i] * (self.res-count): # if hope still exists
dfs(i, rem-coins[i], count+1)

for i in range(lenc):
dfs(i, amount, 0)
return self.res if self.res < 2**31-1 else -1

# Runtime: 156 ms, faster than 98.75% of Python online submissions for Coin Change.
# Memory Usage: 11.7 MB, less than 100.00% of Python online submissions for Coin Change.