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

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        '''
        amount = 11
        coins = [1, 2, 5]

        11 
        = 1 + 10
        = 1 + 1 + 9
        = 1 + 1 + 1 + 8
        ...
        = 1 + 1 + 1 + ... 1 (11 of such ones)
        = 1 + 2 + 1 + 1 + 1 ... + 1 (9 1s and 1 2 coin)
        = 1 + 2 + 2 + 1 ... + 1 (7 1 coins and 2 2 coins)

        '''
        #Global variable coins and it represents all the coins that 
        #we can use
        coins = coins

        #DP function that will be called

        '''
        Base case:
        amount = 1 but i'm exchanging the value with a coin of value 2
        => amount = -1
        => check if amount < 0. If so, return inf

        amount = 0 and i'm the value with a coin of value 1
        => amount = 0
        => Good value

        '''
        @lru_cache(None)
        def dp(amount):
            if amount < 0:
                return inf
            elif amount == 0:
                return 0
            else:
                #This is required because for a given node,
                #There may be several branches branch up to
                #So if one of the branch is finished, but not the other branches, this variable would have stored an intermediate value.
                #Once other branch are done and they have returned a value
                #We can then take the minimum of this intermediate variable
                #and the value that has just been returned.
                number_of_coins_required = inf

                #This represents the exchanging process
                #What it does is loop through all the coins
                #That is available, and the minus the amount
                #By the coin that is selected

                for i in coins:
                    number_of_coins_required = min(number_of_coins_required, 1 + dp(amount - i))
                return number_of_coins_required
        
        #I want to see what kind of value
        #Is returned. If the ans value is inf, it means
        #There is no valid operation. 
        ans = dp(amount)
        if ans == inf:
            return -1
        return ans
36828