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

-w1212

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

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.

3. BFS

待整

References

  1. 322. Coin Change
  2. 花花酱 LeetCode 322. Coin Change
  3. Fast-Python-BFS-Solution
  4. Python, 11-line, 280ms, DFS with early termination, 99% up
  5. 3ms c++, easy to understand!