“零錢兌換”是一道經典的算法題目，其主要問題是：給定不同面額的硬幣和一個總金額，求出湊成總金額所需的最少硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回-1。

解題思路

1. 動態規劃：使用動態規劃是解決零錢兌換問題的常用方法。定義一個數組dp，其中dp[i]表示湊成金額i所需的最少硬幣個數。
2. 狀態轉移方程：對于每個金額i，遍歷所有硬幣面額coin，如果i >= coin，則dp[i] = min(dp[i], dp[i - coin] + 1)。
3. 初始化：dp[0] = 0，因為湊成金額0不需要任何硬幣。對于其他金額，可以初始化為一個較大的數（如amount + 1），表示初始時無法湊成該金額。
4. 結果判斷：最終dp[amount]即為所求，如果dp[amount]仍為初始值，則表示無法湊成總金額，返回-1。

示例代碼（C++）

#include <vector>
#include <algorithm>
using namespace std;int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, amount + 1); // 初始化為一個較大的數dp[0] = 0; // 湊成金額0不需要任何硬幣for (int i = 1; i <= amount; ++i) {for (int coin : coins) {if (i >= coin) {dp[i] = min(dp[i], dp[i - coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];
}

說明

• 輸入：coins是一個整數數組，表示不同面額的硬幣；amount是一個整數，表示總金額。
• 輸出：返回湊成總金額所需的最少硬幣個數，如果無法湊成，則返回-1。

這道題考察了動態規劃的思想和實現能力，是面試中常見的算法題。

狀態轉移方程不太懂

好的，我們來詳細解釋一下“零錢兌換”問題中的狀態轉移方程。

問題背景

假設我們有若干種硬幣，每種硬幣有不同的面額。現在需要湊出一個總金額 amount，目標是用最少的硬幣數量湊出這個金額。

動態規劃中的狀態定義

在動態規劃中，我們需要定義一個狀態來表示問題的子問題。對于零錢兌換問題，我們定義：

• dp[i] 表示湊成金額 i 所需的最少硬幣數量。

狀態轉移方程的含義

狀態轉移方程是動態規劃的核心，它描述了如何從已知的子問題狀態推導出當前問題的狀態。

對于零錢兌換問題，狀態轉移方程是：
dp[i] = min(dp[i], dp[i - coin] + 1)

這個方程的意思是：

• 如果我們想湊成金額 i，可以嘗試用一個面額為 coin 的硬幣。
• 如果用了這個硬幣，那么剩下的金額就是 i - coin。
• 我們已經知道湊成金額 i - coin 所需的最少硬幣數量是 dp[i - coin]。
• 因此，湊成金額 i 的硬幣數量可以是 dp[i - coin] + 1（+1 是因為我們多用了一個硬幣）。
• 但是，湊成金額 i 的方法可能有多種（比如可以用不同面額的硬幣），所以我們要取所有可能方法中的最小值。

具體例子

假設硬幣面額為 [1, 2, 5]，目標金額是 11。

初始化

我們先初始化一個數組 dp，長度為 amount + 1，并將所有值設為一個較大的數（比如 amount + 1），表示初始時認為湊不出這些金額。同時，dp[0] = 0，因為湊成金額 0 不需要任何硬幣。

計算過程

我們逐步計算每個金額的最少硬幣數：

1. 計算 dp[1]：

   • 嘗試用面額為 1 的硬幣：dp[1 - 1] + 1 = dp[0] + 1 = 0 + 1 = 1。
   • 因此，dp[1] = 1。

2. 計算 dp[2]：

   • 嘗試用面額為 1 的硬幣：dp[2 - 1] + 1 = dp[1] + 1 = 1 + 1 = 2。
   • 嘗試用面額為 2 的硬幣：dp[2 - 2] + 1 = dp[0] + 1 = 0 + 1 = 1。
   • 因此，dp[2] = min(2, 1) = 1。

3. 計算 dp[3]：

   • 嘗試用面額為 1 的硬幣：dp[3 - 1] + 1 = dp[2] + 1 = 1 + 1 = 2。
   • 嘗試用面額為 2 的硬幣：dp[3 - 2] + 1 = dp[1] + 1 = 1 + 1 = 2。
   • 因此，dp[3] = min(2, 2) = 2。

4. 計算 dp[4]：

   • 嘗試用面額為 1 的硬幣：dp[4 - 1] + 1 = dp[3] + 1 = 2 + 1 = 3。
   • 嘗試用面額為 2 的硬幣：dp[4 - 2] + 1 = dp[2] + 1 = 1 + 1 = 2。
   • 因此，dp[4] = min(3, 2) = 2。

5. 計算 dp[5]：

   • 嘗試用面額為 1 的硬幣：dp[5 - 1] + 1 = dp[4] + 1 = 2 + 1 = 3。
   • 嘗試用面額為 2 的硬幣：dp[5 - 2] + 1 = dp[3] + 1 = 2 + 1 = 3。
   • 嘗試用面額為 5 的硬幣：dp[5 - 5] + 1 = dp[0] + 1 = 0 + 1 = 1。
   • 因此，dp[5] = min(3, 3, 1) = 1。

……以此類推，直到計算出 dp[11]。

總結

狀態轉移方程 dp[i] = min(dp[i], dp[i - coin] + 1) 的含義是：

• 對于每個金額 i，嘗試用每一種硬幣 coin。
• 如果用了這個硬幣，那么剩下的金額是 i - coin，而湊成 i - coin 的最少硬幣數是已知的（dp[i - coin]）。
• 因此，湊成金額 i 的硬幣數可以是 dp[i - coin] + 1。
• 最后取所有可能方法中的最小值，作為湊成金額 i 的最少硬幣數。

希望這個解釋能幫助你更好地理解狀態轉移方程！

我還是不理解

好的，我來用更通俗的方式解釋“零錢兌換”問題。

---

問題背景

假設你是一名收銀員，顧客需要找零，你手上有不同面額的硬幣。你的任務是用最少的硬幣數量湊出顧客需要的零錢金額。

舉個例子

假設你手上有以下幾種硬幣：

• 1元硬幣
• 3元硬幣
• 4元硬幣

現在顧客需要找零 10元，你會怎么湊呢？

---

思考過程

1. 目標：用最少的硬幣湊出10元。
2. 方法：你可以嘗試不同的組合：
   • 用10個1元硬幣（10個硬幣）
   • 用3個3元硬幣 + 1個1元硬幣（4個硬幣）
   • 用2個4元硬幣 + 2個1元硬幣（4個硬幣）
   • 用1個4元硬幣 + 2個3元硬幣（3個硬幣）

經過比較，你會發現 1個4元硬幣 + 2個3元硬幣 是最優解，只需要 3個硬幣。

---

零錢兌換問題的核心

1. 輸入：

   • 一個硬幣數組，比如 [1, 3, 4]，表示你手上的硬幣面額。
   • 一個目標金額，比如 10，表示需要湊出的金額。

2. 輸出：

   • 返回最少需要的硬幣數量。如果無法湊出目標金額，返回 -1。

3. 難點：

   • 你不能簡單地從最大的硬幣開始湊，因為可能無法湊出目標金額。比如，目標金額是 6元，硬幣面額是 [4, 3, 1]，如果你先用一個4元硬幣，剩下的2元就無法湊出（因為沒有2元硬幣）。

---

動態規劃的思路

動態規劃是一種分步解決問題的方法，它把大問題拆成小問題，逐步求解。

1. 定義狀態：

   • 假設 dp[i] 表示湊出金額 i 所需的最少硬幣數量。

2. 狀態轉移：

   • 假設你已經知道湊出金額 i - coin 所需的最少硬幣數量（dp[i - coin]），那么加上一個面額為 coin 的硬幣，就可以湊出金額 i。
   • 所以，dp[i] = min(dp[i], dp[i - coin] + 1)，意思是：湊出金額 i 的最少硬幣數，要么是之前已經計算好的值，要么是湊出金額 i - coin 的硬幣數加1。

3. 初始化：

   • dp[0] = 0，因為湊出金額0不需要任何硬幣。
   • 其他金額可以初始化為一個很大的數（比如 amount + 1），表示目前無法湊出。

4. 最終結果：

   • 如果 dp[amount] 仍然是初始值（比如 amount + 1），說明無法湊出目標金額，返回 -1。
   • 否則，返回 dp[amount]。

---

用例子解釋動態規劃

假設硬幣面額是 [1, 3, 4]，目標金額是 6，我們逐步計算 dp 數組：

金額（i）	0	1	2	3	4	5	6
dp[i]	0	1	2	1	1	2	2

• 金額0：dp[0] = 0，湊出金額0不需要硬幣。
• 金額1：只能用1個1元硬幣，所以 dp[1] = 1。
• 金額2：只能用2個1元硬幣，所以 dp[2] = 2。
• 金額3：可以用3個1元硬幣（dp[3] = dp[0] + 1 = 1），也可以用1個3元硬幣（dp[3] = 1）。
• 金額4：可以用4個1元硬幣（dp[4] = dp[0] + 1 = 1），也可以用1個4元硬幣（dp[4] = 1）。
• 金額5：可以用5個1元硬幣（dp[5] = dp[0] + 1 = 2），也可以用1個3元硬幣 + 2個1元硬幣（dp[5] = dp[2] + 1 = 2）。
• 金額6：可以用6個1元硬幣（dp[6] = dp[0] + 1 = 2），也可以用2個3元硬幣（dp[6] = dp[0] + 2 = 2）。

最終，湊出金額6最少需要2個硬幣。

---

總結

零錢兌換問題的核心是用最少的硬幣湊出目標金額。動態規劃通過逐步計算每個金額所需的最少硬幣數，最終得到答案。希望這個解釋能幫助你理解！

這回我終于懂了！