Problem Statement: 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.

Is there a way to make my solution faster?
Explanation: dp[curr_amount] stores the minimum number of how many more coins I would need to reach target amount

def coinChange(self, coins: List[int], amount: int) -> int:
        
        if amount == 0:
            return 0
        
        dp = {}                
        def backtrack(curr_amount):            
            if (curr_amount) in dp:
                return dp[curr_amount]
            
            if curr_amount == amount:
                return 0
            
            if curr_amount > amount:
                return inf
                
            
            for coin in coins:
                if (curr_amount) not in dp:
                    dp[curr_amount] = inf
                # Take the minimum number of coins needed given all the possible choices
                dp[curr_amount] = min(dp[curr_amount], 1   backtrack(curr_amount   coin))
                    
            return dp[curr_amount]
        
        res = backtrack(0)
        
        if res == inf:
            return -1
        
        return res

CodePudding user response：

Not sure how to fix your way, but can try to see if this can speed up. It's DP bottom-up approach:

It's kind of follow @joanis thought (inspired by). Thanks.

def min_coin_change(target, coins):
    # bottom up approach
    
    dp = [float("inf") for _ in range(target 1)]
    
    dp[0] = 0
    
    for i in range(1, target 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], 1   dp[i-coin])
    return dp[target] if dp[target] != float("inf") else -1



if __name__ == '__main__':
    coins = [1, 2, 5, 10]
    target = 17

    print(min_coin_change(target, coins))  # 3

    print(min_coin_change(24, coins))      # 4
    print(min_coin_change(124, coins))      # 14

CodePudding user response：

I would suggest the breadth-first search approach.

The idea is as follows:

1. Any value c in coins can be reached in one step
2. If we can reach a value x in s steps, then we can reach x c in s 1 steps, for each c in coins.

So, we can expand the mapping from the target to the minimum steps efficiently by using the queue structure.

from collections import deque

def coinChange(coins: list, target: int):
  # breadth-first search using queue data structure
  v = {0: 0}
  q = deque([0])
  while len(q) > 0:
    cur = q.popleft()
    for coin in coins:
      nxt = cur   coin  # we can reach this value in one more step
      if nxt in v:  # we have already covered this amount in shorter step
        continue
      if nxt == target:  # we have reached the target
        return v[cur]   1 
      if nxt < target:
        # we continue the search only for the values smaller than the target
        # because the value is only increasing
        v[nxt] = v[cur]   1
        q.append(nxt)
  # we could not reach the target value
  return -1

print(coinChange([1, 2, 5, 10], 17))  # 3
print(coinChange([1, 2, 5, 10], 24))  # 4
print(coinChange([1, 2, 5, 10], 124)) # 14
print(coinChange([5, 8], 12))         # -1