给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

**输入：n = 12输出：**3
**解释：**12 = 4 + 4 + 4

示例 2：

**输入：n = 13输出：**2
**解释：**13 = 4 + 9

提示：

1 <= n <= 10(4)

dp[i]表示和为i时的答案

dp[n]的话就要不断减完全平方数，然后取最小的dp[ n-j*j ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            int mid = INT_MAX;
            for (int j = 1; j * j <= i; j++) {
                mid = min(mid, dp[i - j * j]);
            }
            dp[i] = mid + 1;
        }
        return dp[n];
    }
};

四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。

同时四平方和定理包含了一个更强的结论：当且仅当 n!=4^k × (8m+7) 时，n 可以被表示为至多三个正整数的平方和。因此，当 n = 4^k × (8m+7) 时，n 只能被表示为四个正整数的平方和。此时我们可以直接返回 4。

3比较难判断，我们只需要判断ans是否为1或2或4，都不是返回3即可

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
29
class Solution {
public:
    bool isSqrt(int n) {
        int sq = sqrt(n);
        if (sq * sq == n)
            return true;
        return false;
    }

    bool isAns4(int n) {
        while (n % 4 == 0) {
            n /= 4;
        }
        return n % 8 == 7;
    }

    int numSquares(int n) {
        if (isSqrt(n))
            return 1;
        if (isAns4(n))
            return 4;

        for (int i = 1; i * i < n; i++) {
            if (isSqrt(n - i * i))
                return 2;
        }
        return 3;
    }
};