<p>You are given an integer array <code>coins</code> representing coins of different denominations and an integer <code>amount</code> representing a total amount of money.</p>

<p>Return <em>the fewest number of coins that you need to make up that amount</em>. If that amount of money cannot be made up by any combination of the coins, return <code>-1</code>.</p>

<p>You may assume that you have an infinite number of each kind of coin.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> coins = [1,2,5], amount = 11
<strong>Output:</strong> 3
<strong>Explanation:</strong> 11 = 5 + 5 + 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> coins = [2], amount = 3
<strong>Output:</strong> -1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> coins = [1], amount = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= coins.length &lt;= 12</code></li>
	<li><code>1 &lt;= coins[i] &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>0 &lt;= amount &lt;= 10<sup>4</sup></code></li>
</ul>

import heapq
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        """
        Can't simply use the largest coin
        Maybe do preprocessing?
        BFS forward times out, not sure what's faster. Not clear that backward would be faster

        Try Dijkstra's? No, this would be the same
        this wasn't DFS at all, can fix it
        """
        q = []
        d = defaultdict(lambda: float('inf'))

        heapq.heappush(q, (0, 0))

        while q:
            n, a = heapq.heappop(q)
            if a == amount: return n
            if n < d[a]:
                d[a] = n
                for coin in coins:
                    if a + coin <= amount:
                        heapq.heappush(q, (n+1, a + coin))

        return -1

17911