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

# 零钱兑换

# 整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

# 返回可以凑成总金额所需的 最少的硬币个数 。
# 如果没有任何一种硬币组合能组成总金额，返回 -1 。

# 每种硬币的数量是无限的。

# 解題思路：
# 這道問題要求找到最少的硬幣數量來湊成給定的 amount，可以使用動態規劃（Dynamic Programming）來解決。
# 這是一個經典的最優子結構問題，我們可以通過將問題拆解為子問題來解決。

# 動態規劃的思路：
# 定義狀態：
# 定義一個一維數組 dp，其中 dp[i] 表示湊成金額 i 所需的最少硬幣數量。
# 初始時，dp[0] = 0，因為湊成金額 0 所需的硬幣數量是 0。
# 其他的 dp[i] 初始設為 float('inf')，表示初始時無法湊成該金額。

# 轉移方程：
# 我們可以使用每個硬幣來更新 dp 表：對於每個硬幣 coin，遍歷 dp，如果我們選擇該硬幣，則可以更新金額 i 的最少硬幣數量：
# dp[i]=min(dp[i],dp[i−coin]+1)
# 這意味著，如果選擇了硬幣 coin，那麼我們只需要湊成金額 i - coin，並再加上一枚 coin。

# 結果：
# 最終，dp[amount] 中的值就是湊成該金額所需的最少硬幣數量。如果 dp[amount] 依然是 float('inf')，則表示無法湊成該金額，返回 -1。

# 279 322 2915 518 983 264
# 279. Perfect Squares
# 322. Coin Change
# 2915. Length of the Longest Subsequence That Sums to Target
# 518. Coin Change II
# 983. Minimum Cost For Tickets
# 264. Ugly Number II

# DP Bottom Up, math
# O(n * m), s:O(n)
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp [0] = 0

        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[-1] if dp[-1] != float("inf") else -1      # 如果 dp[amount] 還是無限大，說明無法湊成該金額
       
        
        '''
        先 loop coins
        '''
        # 初始化 dp 數組，大小為 amount + 1，初始值為無限大
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0  # 湊成金額 0 所需硬幣數量為 0
        
        # 對於每一個金額，嘗試使用每一個硬幣
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
        # 如果 dp[amount] 還是無限大，說明無法湊成該金額
        return dp[amount] if dp[amount] != float('inf') else -1  
16301