<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, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        # A large value greater than the maximum possible number of coins required, even infinity is fine
        # coins.sort(reverse=True)
        # count = 0
        # for i in coins:
        #     if amount != 0:
        #         count += amount//i
        #         amount %= i
        #     else:
        #         break
        # if amount == 0:
        #     return count
        # else:
        #     return -1
        max_value = float('inf')
        n = len(coins)
        
        dp = [[0 for _ in range(amount+1)] for _ in range(n +1 )]
        
        for i in range(amount + 1):
            dp[0][i] = max_value
        for i in range(1, n+1):
            dp[i][0] = 0

        for i in range(1, amount +1):
            if i % coins[0] == 0:
                dp[1][i] = i// coins[0]
            else:
                dp[1][i] = max_value
        
        for i in range(2, n +1):
            for j in range(1, amount + 1):
                if coins[i-1] <= j:
                    dp[i][j] = min(dp[i-1][j], 1 + dp[i][ j - coins[i-1]])
                else:
                    dp[i][j] = dp[i-1][j]

        # print(dp)
        return dp[n][amount] if dp[n][amount] != float('inf') else -1


    #    # Initialize dp array where dp[i] represents the minimum number of coins needed for amount i
    #    # dp[i] is initialized with max_value, which is essentially infinity
    #    dp = [max_value] * (amount + 1)
       
    #    # Base case: No coins are needed to make the amount 0
    #    dp[0] = 0
       
    #    # Iterate through each coin denomination
    #    for coin in coins:
    #        # Iterate through all amounts from the current coin value to the target amount
    #        for x in range(coin, amount + 1):
    #            # Update dp[x] with the minimum of:
    #            # 1. The current value of dp[x] (minimum coins needed without considering the current coin)
    #            # 2. dp[x - coin] + 1 (minimum coins needed for the remaining amount (x - coin) plus the current coin)
    #            dp[x] = min(dp[x], dp[x - coin] + 1)
       
    #    # If dp[amount] is still max_value, it means the target amount cannot be made up by any combination of the coins
    #    # In that case, return -1 to indicate that it's not possible to make the change
    #    # Otherwise, return dp[amount], which represents the minimum number of coins needed
    #    return dp[amount] if dp[amount] != max_value else -1
18716