算法1完全背包

从多个数选，使得和是m，使得选的数尽量少，我们能快速的想到完全背包

优化后
$ 时间复杂度O(NM),空间复杂度O(M)$，其中 M = sqrt(N)

参考文献

lc究极班

AC代码

class Solution {
public:
    int numSquares(int m) {
        vector<int> v;
        vector<int> f(m + 1, 0x3f);
        int n = 0;
        v.push_back(0);
        for (int i = 1 ; i <= sqrt(m) ; i ++) v.push_back(i * i), n ++;
        //完全背包
        f[0] = 0;
        for (int i = 1 ; i <= n ; i ++){
            for (int j = v[i] ; j <= m ; j ++){
                f[j] = min(f[j], f[j - v[i]] + 1);
            }
        }
        return f[m];

    }
};

算法2数论解法

1.拉格朗日四平方和定理：每个正整数均可表示为4个整数的平方和。该定理能使得最终答案是1,2,3,4其中的一个。

2.勒让德三平方和定理：当n = 4^a^ (8b + 7) ,n不能用3个数的平方和

用上面的两个定理，我们枚举答案是否是1/2/3，否则答案是4。

枚举是答案是1时间复杂度O(1),枚举答案是2时间复杂度O(sqrt(N))，枚举答案是3时间复杂度O(logN)，空间复杂度O(1)

$ 时间复杂度O(logN),空间复杂度O(1)$

参考文献

wzc大佬题解

AC代码

class Solution {
public:
    bool check(int x){
        int t = sqrt(x);
        return t * t == x;
    }

    int numSquares(int n) {
        if (check(n)) return 1;//判断答案为1
        //判断答案为2
        for (int a = 1 ; a <= n / a ; a ++){
            int b = n - a * a;
            if (check(b)) return 2;
        }
        //判断答案为3
        while (n % 4 == 0) n /= 4;
        if ((n - 7) % 8 != 0) return 3;
        return 4;


    }
};