1. 题目
2. 解题思路
此图利用动态规划进行求解，首先，我们求出小于
n
n
n 的所有完全平方数，存放在数组 squareNums 中。
定义 dp[n] 为和为
n
n
n 的完全平方数的最小数量，那么有状态转移方程：
d
p
[
n
]
=
m
i
n
(
d
p
[
n
−
s
q
u
a
r
e
N
u
m
s
[
i
]
]
+
1
,
d
p
[
n
]
)
,
对于任意
s
q
u
a
r
e
N
u
m
s
[
i
]
<
n
dp[n] = min(dp[n-squareNums[i]] + 1, dp[n]), 对于任意 \space squareNums[i] < n
dp[n]=min(dp[n−squareNums[i]]+1,dp[n]),对于任意 squareNums[i]<n
d
p
[
n
]
=
1
，对于
s
q
u
a
r
e
N
u
m
s
[
i
]
=
=
n
dp[n] = 1，对于 \space squareNums[i] == n
dp[n]=1，对于 squareNums[i]==n
3. 代码实现
class Solution {
public:
int numSquares(int n) {
vector<int> squareNums;
for (int i = 1; i < n; ++i) {
if (i * i > n) {
break;
}
squareNums.push_back(i * i);
}
vector<int> dp(n+1, 10000);
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < squareNums.size(); ++j) {
if (squareNums[j] > i) {
break;
} else if (squareNums[j] == i) {
dp[i] = 1;
} else {
dp[i] = min(dp[i], dp[i - squareNums[j]] + 1);
}
}
}
return dp[n];
}
};
时间复杂度为
O
(
n
n
)
O(n\sqrt{n})
O(nn)，第一层循环
n
n
n 次，第二层循环
n
\sqrt{n}
n 次，空间复杂度为
O
(
n
)
O(n)
O(n)，其中 squareNums 占用空间为
O
(
n
)
O(\sqrt{n})
O(n)，也可以省略，直接在第二个循环得到
j
∗
j
j*j
j∗j，dp 占用空间为
O
(
n
)
O(n)
O(n)。