1. 題目

2. 解題思路

此圖利用動態規劃進行求解，首先，我們求出小于 $n$ 的所有完全平方數，存放在數組 squareNums 中。

定義 dp[n] 為和為 $n$ 的完全平方數的最小數量，那么有狀態轉移方程：

$$dp[n]=min(dp[n?squareNums[i]]+1,dp[n]),對于任意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\sqrt{n})$，第一層循環 $n$ 次，第二層循環 $\sqrt{n}$ 次，空間復雜度為 $O(n)$，其中 squareNums 占用空間為 $O(\sqrt{n})$，也可以省略，直接在第二個循環得到 $j?j$，dp 占用空間為 $O(n)$。