题目

核心思路

动态规划

由于这道题我是在动态规划的分类中找的，所以也就第一时间往DP的方向靠。整体思路就是：要求 dp[i] 时，dp[i] 的取值必然是所有 dp[i] 前面元素 dp[j] 中，满足i - j是完全平方数条件的 dp[j] 的最小值加一，按照动态规划思想很容易会得到这样的计算方法：

        for(int i = 0; i < n; i++){
            if((i + 1) == num * num){
                //该数为完全平方数
                dp[i] = 1;
                num++;
                nums.add(i + 1);
            }else{
                //不是完全平方数，遍历求解过的结果，寻找最少的个数
                dp[i] = i + 1;//最坏情况 i + 1 个1相加
                for(int j = 0; j < i; j++){
                    if(nums.contains(i - j)){
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
        }

不过这样提交是超时的，需要想办法优化时间复杂度，而外层循环肯定是不可避免的了，所以只能考虑优化内层循环。可以注意到只有 i - j 为完全平方数时，才会更新 dp 数组，所以可以反过来遍历小于 i 的所有完全平方数，并更新 dp[i] ，就可以大幅度减少循环的次数，得到如下的代码：

public int numSquares(int n) {
        if(Math.round(Math.sqrt(n)) == Math.sqrt(n)){
            return 1;
        }
        int[] dp = new int[n];
        int num = 1;
        int[] nums = new int[(int)Math.sqrt(n) + 1];
        for(int i = 0; i < nums.length; i++){
            nums[i] = (i + 1) * (i + 1);
        }

        for(int i = 0; i < n; i++){
            if((i + 1) == num * num){
                //该数为完全平方数
                dp[i] = 1;
                num++;
            }else{
                //不是完全平方数，遍历求解过的结果，寻找最少的个数
                dp[i] = i + 1;//最坏情况 i + 1 个1相加
                for(int j = (int)Math.sqrt(i + 1) - 1; j >= 0; j--){
                    dp[i] = Math.min(dp[i], dp[i - nums[j]] + 1);
                }
            }
        }
        return dp[n - 1];
    }

这里存储完全平方数当然也可以使用集合动态的存储，不过由于存储的值本来就与数组下标存在联系，直接使用数组就够用了而且省去了维护集合所需要的时间。

贪心算法

我个人只考虑到了如上的方法，虽然猜到了直接从n入手可以更快，不过死活也没想出思路，参考了题解的贪心算法。思路：由于最终要求解的是最少的组合为n的完全平方数的个数，所以我们可以贪心的从1到n枚举个数，并进行验证，只要满足条件即可返回作为最终结果。由于这种方法直接通过最终结果的个数来进行遍历，递归深度和时间复杂度都大大降低，效率较高。
这之中最重要的就是验证给定的数n能否拆分为count个完全平方数。而验证的方法，可以使用递归，遍历完全平方数表，然后交给递归验证即可。

    private HashSet<Integer> nums = new HashSet<Integer>();
    public boolean is_divided_by(int n, int count){
        if(count == 1){
            return nums.contains(n);
        }
        for(Integer temp : nums){
            if(is_divided_by(n - temp, count - 1)){
                return true;
            }
        }
        return false;
    }

递归过程还是比较简单的，剩下需要完成的就是生成完全平方数表，循环调用该验证方法即可。

完整代码

class Solution {

    private HashSet<Integer> nums = new HashSet<Integer>();
    public boolean is_divided_by(int n, int count){
        if(count == 1){
            return nums.contains(n);
        }
        for(Integer temp : nums){
            if(is_divided_by(n - temp, count - 1)){
                return true;
            }
        }
        return false;
    }

    public int numSquares(int n) {
        int len = (int)Math.sqrt(n) + 1;
        for(int i = 0; i < len; i++){
            nums.add(i * i);
        }

        for(int i = 1; i < n; i++){
            if(is_divided_by(n, i)){
                return i;
            }
        }
        return n;
    }
}

数学定理法

本来以为通过贪心算法已经可以得到最优解了，谁知道还有更加高效的方法，分别应用三平方定理和四平方定理进行验证，就可以在O(√n)的时间复杂度下完成验证，定理牛批！

class Solution {

    public int numSquares(int n) {
        int temp = n;
        //验证是否满足三平方定理
        while(temp % 4 == 0){
            temp /= 4;
        }
        if(temp % 8 == 7){
            return 4;
        }

        if(isSquare(n)){
            return 1;
        }

        for(int i = 1; i <= (int)Math.sqrt(n); i++){
            if(isSquare(n - i * i)){
                return 2;
            }
        }
        return 3;
    }

    //判断n是否为完全平方数
    public boolean isSquare(int n ){
        int sq = (int)Math.sqrt(n);
        return n == sq * sq;
    }
}

具体的定理如何使用可以参考官方题解，虽然没有给出定理证明，但是核心思路和怎么运用都已经给出了。如果想了解证明的可以参考勒让德的三平方定理(维基百科你懂得)

总结

算法学到最后主要还是思维，这句话真的没错，数学通过定理的证明和使用就达到了使用普通算法达不到的时间复杂度，太让人佩服了，通过这道题也算是浅薄的了解了三平方定理和拉格朗日平方和定理，收获蛮多。
如果文章有写的不正确的地方还请指出。感恩相遇~

279-完全平方数-数学定理教做人