279. 完全平方数

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

考点

  • 完全背包

思路

完全背包的裸题，只不过体积为每个数的平方而已

二维：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int numSquares(int n) {
    // f[i][j]: 考虑前i个，和凑成j的数字个数，取最小
    int f[105][10005];
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i * i <= n; ++i) {
      int x = i * i;
      for (int j = 0; j <= n; ++j) {
        f[i][j] = min(f[i][j], f[i - 1][j]);
        if (j >= x) f[i][j] = min(f[i][j], f[i][j - x] + 1);
      }
    }
    return f[(int)sqrt(n)][n];
  }
};

压缩成一维：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
 public:
  int numSquares(int n) {
    // f[i][j]: 考虑前i个，和凑成j的数字个数，取最小
    int f[10005];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i * i <= n; ++i) {
      int x = i * i;
      for (int j = x; j <= n; ++j) f[j] = min(f[j], f[j - x] + 1);
    }
    return f[n];
  }
};