2025-12-06：硬幣面值還原。用go語言，給出一個從 1 開始索引的整數數組 numWays，其中 numWays[i] 表示用若干種固定面額且每種可重複使用的硬幣，湊出金額 i 的方案數。所有面額都是正整數，且最大不會超過 numWays 的長度。目前具體的面額信息丟失了，你需要推斷出可能導致該 numWays 的硬幣面額集合。

輸出應為一個按升序排列的不重複面額列表（即所有可能出現的面額）；如果不存在任何能生成該 numWays 的面額組合，則返回空數組。

輸入： numWays = [0,1,0,2,0,3,0,4,0,5]。

輸出： [2,4,6]。

解釋：

題目來自力扣3592。

🔍 問題解決步驟詳解

1. 初始化動態規劃數組

   • 創建一個長度為 n+1 的數組 f（其中 n 是 numWays 的長度），用於記錄使用當前已推斷出的硬幣面額組合，湊出金額 0 到 n 的方案數。
   • 將 f[0] 初始化為 1，表示湊出金額 0 的方案數為 1（即不取任何硬幣）。對於 i 從 1 到 n，f[i] 的初始值均為 0。

2. 遍歷每個金額並檢查方案數

   • 從金額 i = 1 開始遍歷至 i = n（對應 numWays 的索引為 i-1）：
     • 獲取 numWays[i-1] 的值，即題目給定的湊出金額 i 的方案數，記為 ways。
     • 比較 ways 與當前動態規劃數組計算出的方案數 f[i]：
       • 情況一：ways == f[i]
         • 説明當前已推斷出的硬幣面額組合已經能正確生成金額 i 的方案數，無需添加新的面額。直接繼續處理下一個金額 i+1。
       • 情況二：ways != f[i]
         • 此時需要嘗試添加新的面額以匹配給定的方案數。檢查條件 ways - 1 == f[i] 是否成立：
           • 如果成立，則表示可以通過添加一個面額為 i 的硬幣來彌補方案數的差距。將面額 i 加入結果集 ans，並執行下一步的完全揹包更新。
           • 如果不成立，則説明無法通過添加面額 i 來滿足給定的方案數，立即返回空數組 nil，表示不存在可行的硬幣面額組合。

3. 更新動態規劃數組（完全揹包更新）

   • 當添加了新的面額 i 後，需要更新動態規劃數組 f 以反映新面額對後續金額方案數的影響。這個過程類似於解決完全揹包問題。
   • 具體操作是：對於金額 j 從 i 到 n（從小到大），執行 f[j] += f[j - i]。這表示，對於每個金額 j，新增的方案數等於使用新面額 i 後，湊出金額 j-i 的方案數（因為加上一個面額 i 的硬幣即可湊出金額 j）。 通過這樣的更新，f 數組能動態地記錄當前所有已選面額組合下的方案數。

4. 輸出結果

   • 如果成功遍歷完所有金額 1 到 n 且沒有返回空數組，則收集到的結果集 ans 就是按升序排列的可能硬幣面額集合（因為 i 是遞增遍歷的）。

⏱ 複雜度分析

• 時間複雜度：O(n^2)。

  • 需要遍歷每個金額 i（從 1 到 n），共 n 次循環。
  • 在最壞情況下，每次循環都可能需要更新動態規劃數組（內層循環從 i 到 n），內層循環的次數平均約為 n/2。
  • 因此，總體時間複雜度為平方級別 O(n^2)。

• 空間複雜度：O(n)。

  • 主要空間開銷來自動態規劃數組 f，其大小為 n+1，因此額外空間複雜度為線性 O(n)。

💎 核心思路總結

這個算法的核心在於貪心策略和動態規劃的結合。它從小到大依次考慮每個金額，通過對比給定方案數與當前計算方案數的差異，動態地推斷出必須存在的硬幣面額，並利用完全揹包的思想更新方案數。其正確性依賴於硬幣面額是正整數且不超過 n 的條件，從而保證瞭解的唯一性（如果存在）。

Go完整代碼如下：

package main

import (
	"fmt"
)

func findCoins(numWays []int) (ans []int) {
	n := len(numWays)
	f := make([]int, n+1)
	f[0] = 1
	for i := 1; i <= n; i++ {
		ways := numWays[i-1]
		if ways == f[i] {
			continue
		}
		if ways-1 != f[i] {
			return nil
		}
		ans = append(ans, i)
		// 現在得到了一個大小為 i 的物品，用 i 計算完全揹包
		for j := i; j <= n; j++ {
			f[j] += f[j-i]
		}
	}
	return
}

func main() {
	numWays := []int{0, 1, 0, 2, 0, 3, 0, 4, 0, 5}
	result := findCoins(numWays)
	fmt.Println(result)
}

Python完整代碼如下：

# -*-coding:utf-8-*-

from typing import List

def findCoins(numWays: List[int]) -> List[int]:
    n = len(numWays)
    f = [0] * (n + 1)
    f[0] = 1
    ans = []
    
    for i in range(1, n + 1):
        ways = numWays[i - 1]
        if ways == f[i]:
            continue
        if ways - 1 != f[i]:
            return None
        ans.append(i)
        # 現在得到了一個大小為 i 的物品，用 i 計算完全揹包
        for j in range(i, n + 1):
            f[j] += f[j - i]
    
    return ans

def main():
    numWays = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5]
    result = findCoins(numWays)
    print(result)

if __name__ == "__main__":
    main()

C++完整代碼如下：

#include <iostream>
#include <vector>
using namespace std;

vector<int> findCoins(const vector<int>& numWays) {
    int n = numWays.size();
    vector<int> f(n + 1, 0);
    vector<int> ans;

    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        int ways = numWays[i - 1];
        if (ways == f[i]) {
            continue;
        }
        if (ways - 1 != f[i]) {
            return {};  // 返回空vector
        }
        ans.push_back(i);
        // 現在得到了一個大小為 i 的物品，用 i 計算完全揹包
        for (int j = i; j <= n; j++) {
            f[j] += f[j - i];
        }
    }
    return ans;
}

int main() {
    vector<int> numWays = {0, 1, 0, 2, 0, 3, 0, 4, 0, 5};
    vector<int> result = findCoins(numWays);

    // 輸出結果
    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i != result.size() - 1) {
            cout << ", ";
        }
    }
    cout << "]" << endl;

    return 0;
}