279. 完全平方数

维护一个数组，用于存储下标所对应的数的完全平方数最小个数，因此就可以将较大的数分解为较小数的和，也就可以转移状态。

假设 f[0] = 0 ，并且每个 f 函数必然可以由一个比它小的 f 函数与一个选定的 n 构成，此时 f[n] = 1 + minn ，其中 1 表示选定的数 n ，它所代表的个数为 1 ；minn 表示当前最小的一组数的构成。

在遍历前令 minn = INF ，那么对于 f[n = 1] ，从完全平方数的最小值 1 开始遍历，发现 1 * 1 没有超过 n = 1 ，那么 f[1] 的构成就有如下关系：

f[n] = 1 + f[n - 1 * 1] ，其中 n = 1 ；

因此上式可化简为 f[1] = 1 + f[0] ，也就是说此时需要考虑 f[0] 的值是否可以用来更新 minn ，如果能使它变得更小，则表示这种 f 函数的构成方式更优；

对 minn 进行更新，此时 f[1] = 1 + minn = 1 + f[0] = 1；

同理可得 f[2] = 2 ，f[3] = 3 ；

考虑 f[4] ，从最小值 1 开始遍历：

• f[4] = 1 + f[4 - 1 * 1] = 1 + f[3]
• f[4] = 1 + f[4 - 2 * 2] = 1 + f[0]

可以发现第一种情况的 minn = f[3] = 3 ，第二种情况的 minn = f[0] = 0 ，显然第二种情况更优，因此 f[4] = 1 + minn = 1

按此规则更新至所求 n 即可得出最终解，时间复杂度为 O ( n n ) O(nsqrt n) O(nn ​) ，空间复杂度为 O ( n ) O(n) O(n) ：

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

若 n = 4 k ( 8 m + 7 ) n = 4^k(8m+7) n=4k(8m+7) ，则 n 可由 4 个完全平方数表示，否则至多由 3 个完全平方数表示。

因此将剩下的数分为完全平方数、两个完全平方数之和与其他三类即可，分别对应返回值为 1，2，3。

时间复杂度 O(n)，空间复杂度O(1)，时间复杂度可优化。

class Solution {
public:
    int numSquares(int n) {
        //判断结果是不是 4
        int x = n;
        while(x % 4 == 0)
            x /= 4;
        if(x % 8 == 7)
            return 4;
        if(int(sqrt(n)) * int(sqrt(n)) == n)
            return 1;
        for(int i = 1; i < sqrt(n); ++i)
            for(int j = 1; j < sqrt(n); ++j)
                if(i * i + j * j == n)
                    return 2;
        return 3;
    }
};