最少硬幣問題

最少硬幣問題（Least Coin Problem）是一個數學優化問題，目標是在給定一定金額的情況下，找出使用最少種類的硬幣來支付該金額的方法。這個問題有許多變體，可以根據不同的條件進行調整，例如：

1. 硬幣種類的限制：可以使用的硬幣種類有限，例如只有1分、5分、10分和25分的硬幣。
2. 金額的限制：需要支付的總金額有一定的範圍。
3. 最少硬幣數量：目標是使用最少種類的硬幣來支付金額，而不是最少數量的硬幣。

解決這個問題通常涉及遞歸算法或動態規劃方法。一個簡單的遞歸算法可以這樣工作：

1. 從最大的硬幣面值開始檢查，看看是否可以用它來支付剩餘的金額。
2. 如果可以，記錄下使用該硬幣的次數，並將剩餘金額減去該硬幣的面值，然後重複步驟1。
3. 如果不能，繼續檢查下一個較小的硬幣面值，直到找到一種支付方式或者剩餘金額為零（表示支付完成）。

動態規劃方法則會使用一個狀態陣列來記錄已經解決的子問題的答案，以便重複使用的時候可以直接查詢，而不必重新計算。這種方法可以避免重複計算，提高效率。

例如，假設我們有1分、5分、10分和25分的硬幣，需要支付的金額是67分。我們可以使用以下算法來找出最少硬幣種類的支付方式：

1. 從最大的硬幣面值25分開始檢查。
2. 我們可以用3個25分的硬幣來支付67分，但是這樣使用了3種不同的硬幣（因為我們還使用了1分和5分的硬幣）。
3. 接著檢查下一個較小的硬幣面值，即10分。
4. 我們可以用1個25分、1個10分和1個5分的硬幣來支付67分，這樣只使用了2種不同的硬幣。
5. 因為2種硬幣的方案比3種硬幣的方案更好，所以我們找到了一個更好的支付方式。

最終答案是使用1個25分、1個10分和1個5分的硬幣來支付67分，這是最少硬幣種類的支付方式。