3592. 硬币面值还原

发表于 分类于 阅读次数： Waline： 本文字数： 382 阅读时长 ≈ 1 分钟

考点

  • 完全背包

思路

由题，面值的范围是1 ~ n，而和的范围也是1 ~ n

以和为4为例，要拼成4，只有1 、 2、 3这三个面额组成，或者只有一个4

所以我们只需要判定：

  • 如果1、2、3组成4的情况等于numWays[4]（编程时为3），说明4不存在
  • 如果1、2、3组成4的情况再加1等于numWays[4]（编程时为3），说明4存在
  • 其余情况都非法，因为不可能大于numWays[4]，直接返回

暴力的二维：

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:
  vector<int> findCoins(vector<int>& numWays) {
    vector<int> ans;
    // 面值、和的范围都是1 ~ n
    int n = numWays.size();
    int f[105][105];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      if (numWays[i - 1] == f[i - 1][i] + 1) {
        // 说明i存在
        ans.push_back(i);
        for (int j = 0; j <= n; ++j) {
          f[i][j] += f[i - 1][j];
          if (j >= i) f[i][j] += f[i][j - i];
        }
      } else if (numWays[i - 1] == f[i - 1][i]) {
        // 说明i不存在
        for (int j = 0; j <= n; ++j) f[i][j] += f[i - 1][j];
      } else {
        // 其他情况非法，直接返回空
        return vector<int>();
      }
    }
    return ans;
  }
};

压缩后的一维：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  vector<int> findCoins(vector<int>& numWays) {
    vector<int> ans;
    // 面值、和的范围都是1 ~ n
    int n = numWays.size(), f[105];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
      if (numWays[i - 1] == f[i] + 1) {
        // 说明i存在
        ans.push_back(i);
        for (int j = i; j <= n; ++j) f[j] += f[j - i];
      } else if (numWays[i - 1] == f[i]) {
        // 说明i不存在
      } else {
        // 其他情况非法，直接返回空
        return vector<int>();
      }
    }
    return ans;
  }
};