跳转至

3592. 硬币面值还原

题目描述

给你一个 从 1 开始计数 的整数数组 numWays，其中 numWays[i] 表示使用某些 固定 面值的硬币（每种面值可以使用无限次）凑出总金额 i 的方法数。每种面值都是一个 正整数 ，并且其值 最多 为 numWays.length。

然而，具体的硬币面值已经 丢失 。你的任务是还原出可能生成这个 numWays 数组的面值集合。

返回一个按从小到大顺序排列的数组，其中包含所有可能的 唯一 整数面值。

如果不存在这样的集合，返回一个 空 数组。

 

示例 1：

输入： 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]。

示例 2：

输入： numWays = [1,2,2,3,4]

输出： [1,2,5]

解释：

金额 方法数 解释
1 1 唯一的方法是 [1]。
2 2 可以用 [1, 1] 或 [2]。
3 2 可以用 [1, 1, 1] 或 [1, 2]。
4 3 可以用 [1, 1, 1, 1]、[1, 1, 2] 或 [2, 2]。
5 4 可以用 [1, 1, 1, 1, 1]、[1, 1, 1, 2]、[1, 2, 2] 或 [5]。

示例 3：

输入： numWays = [1,2,3,4,15]

输出： []

解释：

没有任何面值集合可以生成该数组。

 

提示：

  • 1 <= numWays.length <= 100
  • 0 <= numWays[i] <= 2 * 108

解法

方法一

思考

\(\textit{numWays}[i]\) 是用未知面值凑 \(i+1\) 的完全背包方案数。从 \(1\) 到 \(n\) 扫描：若当前金额在已有面值下的方案数比 \(\textit{numWays}\) 少 \(1\)，则必须引入该金额作为新面值；多了或对不上则无解。

每认定一个面值，就用完全背包更新后续方案数。扫描结束即得递增的面值列表，或在矛盾时返回空数组。

1


1


1


1

评论