<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>

'''Return the fewest number of coins that you need to make up that amount.
    - using the array coins, and figure out how many coins minimum are needed to make up amount


If that amount of money cannot be made up by any combination of the coins, return -1.
    - what does it mean if it cant be made?
        all coin values > amount, so there is no possible way to make exact amount with coins

- infinite number of coins
    - i can reuse coins

- count of minimum coins needed.
    - counting
    - minimum
    - compare against every other count

coins = coins, i = individual coin

amount =  amount

decisions?

take: amount - i
    take: amount - i
    skip i = i + 1
skip : i + 1'''

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        global res
        res = amount + 1
        @cache
        def minimumCoins_startingWith_toMake(x: int) -> int:
            if x == 0:
                return 0
            res = 10**5
            for i in range(len(coins)):
                if coins[i] <= x:
                    curr = minimumCoins_startingWith_toMake(x - coins[i])
                    res = min(curr + 1, res)

            return res

        result = minimumCoins_startingWith_toMake(amount)

        return (-1 if result == 10**5 else result)

        




        
42463