279. Perfect Squares.md

279. Perfect Squares

思路

求n最少由多少正整数平方和得到.

思路一

很容易想到用动态规划, 我们先开辟一个长度为n+1初始值全为INT_MAX的数组dp, dp[i]表示正整数i能少能由多个完全平方数组成, 则dp[0]=0. 我们从前往后更新dp[i]:

for all 1 <= j <= sqrt(i):
  dp[i]=min(dp[i - j*j] + 1)

更新完毕后返回dp[n]即可.

思路二

再看一个数学解法. 首先需要知道两个定理:

1. 四平方和定理: 每个正整数均可表示为4个整数(可为0)的平方和;
2. Legendre三平方和定理: 当且仅当n不能表示成(4^a)*(8b+7)时n才可以表示成3个整数(可为0)的平方和,其中a和b是任意非负整数.

所以结果只可能是1,2,3或4, 而且如果m = 4*n, 那么m的结果和n的结果是一样的.

C++

思路一

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

思路二

class Solution {
public:
    int numSquares(int n) {
        while (n % 4 == 0) n /= 4; // 如果m = 4*n, 那么m的结果和n的结果是一样的
        if (n % 8 == 7) return 4; // 不满足Legendre三平方和定理
        // 判断是否可以用1个或两个正数的平方和表示
        for (int a = 0; a * a <= n; ++a) {
            int b = sqrt(n - a * a);
            if (a * a + b * b == n) {
                return a == 0 ? 1 : 2;
            }
        }
        return 3;
    }
};