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 <= 1000 <= numWays[i] <= 2 * 10^8
遍历判断每个数字是否可行，记忆化搜索dp，On3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public List<Integer> findCoins(int[] numWays) {
List<Integer> res = new ArrayList<>();
int n = numWays.length;
for (int tg = 1; tg <= n; tg++) {
int numWay = numWays[tg-1];
int num = dfs(0, tg, res, new int[res.size()][tg+1]);
if (num > numWay) {
return new ArrayList<>();
} else if (num < numWay) {
res.add(tg);
num = dfs(0, tg, res, new int[res.size()][tg+1]);
if (num != numWay) return new ArrayList<>();
}
}
return res;
}
private int dfs(int i, int tg, List<Integer> list, int[][] memo) {
if (list.size() == 0) return 0;
if (i >= list.size()) return tg == 0 ? 1 : 0;
if (memo[i][tg] != 0) return memo[i][tg];
int x = list.get(i), res = 0;
for (int cur = 0; cur <= tg; cur += x) {
res += dfs(i+1, tg-cur, list, memo);
}
return memo[i][tg] = res;
}
}
|
遍历判断每个数字是否可行 + 递推dp，On3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public List<Integer> findCoins(int[] numWays) {
List<Integer> res = new ArrayList<>();
int n = numWays.length;
for (int tg = 1; tg <= n; tg++) {
int numWay = numWays[tg-1];
int num = getNum(res, tg);
if (num > numWay) {
return new ArrayList<>();
} else if (num < numWay) {
res.add(tg);
num = getNum(res, tg);
if (num != numWay) return new ArrayList<>();
}
}
return res;
}
private int getNum(List<Integer> list, int tg) {
int[][] f = new int[list.size()+1][tg+1];
f[0][0] = 1;
for (int i = 0; i < list.size(); i++) {
for (int j = 0; j <= tg; j++) {
f[i+1][j] += f[i][j];
if (j-list.get(i) < 0) continue;
f[i+1][j] += f[i+1][j-list.get(i)];
}
}
return f[list.size()][tg];
}
}
|
直接用完全背包写法，每次只需要On更新完全背包即可，不要每次重新构造完全背包，On2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public List<Integer> findCoins(int[] numWays) {
List<Integer> res = new ArrayList<>();
int n = numWays.length;
int[] f = new int[n+1];
f[0] = 1;
for (int tg = 1; tg <= n; tg++) {
int numWay = numWays[tg-1];
if (numWay == f[tg]) continue;
if (numWay != f[tg] + 1) return List.of();
res.add(tg);
for (int i = tg; i <= n; i++) {
f[i] += f[i-tg];
}
}
return res;
}
}
|
