2025-12-06：硬币面值还原。用go语言，给出一个从 1 开始索引的整数数组 numWays，其中 numWays[i]

福大大架构师每日一题

发布于 2025-12-19 09:37:35

340

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

解释：

金额	方法数	解释
1	0	无法用硬币凑出总金额 1。
2	1	唯一的方法是 [2]。
3	0	无法用硬币凑出总金额 3。
4	2	可以用 [2, 2] 或 [4]。
5	0	无法用硬币凑出总金额 5。
6	3	可以用 [2, 2, 2]、[2, 4] 或 [6]。
7	0	无法用硬币凑出总金额 7。
8	4	可以用 [2, 2, 2, 2]、[2, 2, 4]、[2, 6] 或 [4, 4]。
9	0	无法用硬币凑出总金额 9。
10	5	可以用 [2, 2, 2, 2, 2]、[2, 2, 2, 4]、[2, 4, 4]、[2, 2, 6] 或 [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] {
            returnnil
        }
        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 importList

deffindCoins(numWays: List[int]) -> List[int]:
    n = len(numWays)
    f = [0] * (n + 1)
    f[0] = 1
    ans = []
    
    for i inrange(1, n + 1):
        ways = numWays[i - 1]
        if ways == f[i]:
            continue
        if ways - 1 != f[i]:
            returnNone
        ans.append(i)
        # 现在得到了一个大小为 i 的物品，用 i 计算完全背包
        for j inrange(i, n + 1):
            f[j] += f[j - i]
    
    return ans

defmain():
    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>
usingnamespace 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;

    return0;
}