我如何提高其运行时间

Question

问题陈述：您将为您提供一个整数阵列硬币，代表代表不同宗派的硬币和代表总金额的整数数量。返回您需要弥补该金额的最少的硬币。如果硬币的任何组合无法弥补这笔钱，请返回-1。您可能会假设每种硬币的无限数量。

有没有办法使我的解决方案更快？
说明：DP [Curr_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

Answer 1

不确定如何修复自己的方式，但可以尝试查看是否可以加快加速。这是DP自下而上的方法：

有点遵循@Joanis思想（灵感来自）。谢谢。

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

Answer 2

我建议您采用广度优先的搜索方法。

该想法如下：

1. 可以在一个步骤中达到一步。
2. in Coins中的任何值c ，如果我们可以在s中达到值x，则步骤，然后我们可以在s+1步骤中访问x+c，对于硬币中的每个c。

因此，我们可以使用队列结构有效地将映射从目标扩展到最小步骤。

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