题目

给你一个整数 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

  解题方法

  动态规划

  与 322. 零钱兑换 相同，只不过物品变成1*1, 2*2, ...。由于物品一定有1存在，所以递推的过程中可以不用考虑dp[j-i*i]==INT_MAX的情况。
  C++代码：

  class Solution {
  public:
    int numSquares(int n) {
        int max_num = sqrt(n);
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        for(int i=1; i<=max_num; i++) {
            for(int j=i*i; j<=n; j++) {
                dp[j] = min(dp[j], dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
  };
  

  数学推导

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

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

当 n≠4^k×(8m+7) 时，我们需要判断到底多少个完全平方数能够表示 n，我们知道答案只会是 1,2,3 中的一个：

• 答案为 1 时，则必有 n 为完全平方数，这很好判断；
• 答案为 2 时，则有 n=a^2+b^2，我们只需要枚举所有的 (1≤a≤n)，判断 n-a^2是否为完全平方数即可；
• 答案为 3 时，我们很难在一个优秀的时间复杂度内解决它，但我们只需要检查答案为 11 或 22 的两种情况，即可利用排除法确定答案。
• 
  

时间复杂度：O(n^0.5)，空间复杂度：O(1)。其中 n 为给定的正整数。最坏情况下答案为3，我们需要运行所有的判断，而判断答案是否为 1 的时间复杂度为 O(1)，判断答案是否为 4 的时间复杂度为 O(logn)，剩余判断为O(n^0.5)。
C++代码：

class Solution {
public:
    bool issqrt(int n) {
        int s = sqrt(n);
        return s*s==n;
    }

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

    int numSquares(int n) {
        if(is4sqrt(n))  return 4;
        if(issqrt(n))   return 1;
        for(int i=1; i<=sqrt(n); i++) {
            if(issqrt(n-i*i))   return 2;
        }
        return 3;
    }
};