0%

[Leetcode]279. Perfect Squares(C++)

题目描述

题目链接:279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

例子

例子 1

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4

例子 2

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9

解题思路

这道题可能一下子想不到用动态规划来做。但是如果如果我们把 (1 ~ n) 中任意一个数看成 n = a + b;那么就可以求解 min_nums(n) = min_nums(a) + min_nums(b),因此我们只要遍历所有的相加组合,进行最小化更新即可。而在这其中,由于要考虑的是平方数相加,所以我们只需要更新包括平方数相加的组合,具体如下:

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
#include <limits.h>

#include <cmath>
#include <vector>
class Solution {
public:
int numSquares(int n) {
std::vector<int> num_squares(n + 1, INT_MAX);
num_squares[0] = 0;

// 遍历所有 sqrt(n) 用来构造平方数
for (int i = 1; i <= std::sqrt(n); ++i) {
for (int j = 1; j <= n; j++) {
// 对每一个大于 i * i 的数,有以下相加组合:
// a = i * i, b = j - i * i, j = a + b
// num_squares[j] = num_squares[a] + num_squares[b]
// = 1 + num_squares[j]
if (j - i * i >= 0) {
num_squares[j] =
std::min(num_squares[j], 1 + num_squares[j - i * i]);
}
}
}
return num_squares[n];
}
};
  • 时间复杂度: O(n*sqrt(n))
  • 空间复杂度: O(n)

GitHub 代码同步地址: 279.PerfectSquares.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions