題目

核心思路

動(dòng)態(tài)規(guī)劃

由于這道題我是在動(dòng)態(tài)規(guī)劃的分類中找的，所以也就第一時(shí)間往DP的方向靠。整體思路就是：要求 dp[i] 時(shí)，dp[i] 的取值必然是所有 dp[i] 前面元素 dp[j] 中，滿足i - j是完全平方數(shù)條件的 dp[j] 的最小值加一，按照動(dòng)態(tài)規(guī)劃思想很容易會(huì)得到這樣的計(jì)算方法：

        for(int i = 0; i < n; i++){
            if((i + 1) == num * num){
                //該數(shù)為完全平方數(shù)
                dp[i] = 1;
                num++;
                nums.add(i + 1);
            }else{
                //不是完全平方數(shù)，遍歷求解過(guò)的結(jié)果，尋找最少的個(gè)數(shù)
                dp[i] = i + 1;//最壞情況 i + 1 個(gè)1相加
                for(int j = 0; j < i; j++){
                    if(nums.contains(i - j)){
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
        }

不過(guò)這樣提交是超時(shí)的，需要想辦法優(yōu)化時(shí)間復(fù)雜度，而外層循環(huán)肯定是不可避免的了，所以只能考慮優(yōu)化內(nèi)層循環(huán)?？梢宰⒁獾街挥?i - j 為完全平方數(shù)時(shí)，才會(huì)更新 dp 數(shù)組，所以可以反過(guò)來(lái)遍歷小于 i 的所有完全平方數(shù)，并更新 dp[i] ，就可以大幅度減少循環(huán)的次數(shù)，得到如下的代碼：

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){
                //該數(shù)為完全平方數(shù)
                dp[i] = 1;
                num++;
            }else{
                //不是完全平方數(shù)，遍歷求解過(guò)的結(jié)果，尋找最少的個(gè)數(shù)
                dp[i] = i + 1;//最壞情況 i + 1 個(gè)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];
    }

這里存儲(chǔ)完全平方數(shù)當(dāng)然也可以使用集合動(dòng)態(tài)的存儲(chǔ)，不過(guò)由于存儲(chǔ)的值本來(lái)就與數(shù)組下標(biāo)存在聯(lián)系，直接使用數(shù)組就夠用了而且省去了維護(hù)集合所需要的時(shí)間。

貪心算法

我個(gè)人只考慮到了如上的方法，雖然猜到了直接從n入手可以更快，不過(guò)死活也沒想出思路，參考了題解的貪心算法。思路：由于最終要求解的是最少的組合為n的完全平方數(shù)的個(gè)數(shù)，所以我們可以貪心的從1到n枚舉個(gè)數(shù)，并進(jìn)行驗(yàn)證，只要滿足條件即可返回作為最終結(jié)果。由于這種方法直接通過(guò)最終結(jié)果的個(gè)數(shù)來(lái)進(jìn)行遍歷，遞歸深度和時(shí)間復(fù)雜度都大大降低，效率較高。
這之中最重要的就是驗(yàn)證給定的數(shù)n能否拆分為count個(gè)完全平方數(shù)。而驗(yàn)證的方法，可以使用遞歸，遍歷完全平方數(shù)表，然后交給遞歸驗(yàn)證即可。

    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;
    }

遞歸過(guò)程還是比較簡(jiǎn)單的，剩下需要完成的就是生成完全平方數(shù)表，循環(huán)調(diào)用該驗(yàn)證方法即可。

完整代碼

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;
    }
}

數(shù)學(xué)定理法

本來(lái)以為通過(guò)貪心算法已經(jīng)可以得到最優(yōu)解了，誰(shuí)知道還有更加高效的方法，分別應(yīng)用三平方定理和四平方定理進(jìn)行驗(yàn)證，就可以在O(√n)的時(shí)間復(fù)雜度下完成驗(yàn)證，定理牛批！

class Solution {

    public int numSquares(int n) {
        int temp = n;
        //驗(yà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是否為完全平方數(shù)
    public boolean isSquare(int n ){
        int sq = (int)Math.sqrt(n);
        return n == sq * sq;
    }
}

具體的定理如何使用可以參考官方題解，雖然沒有給出定理證明，但是核心思路和怎么運(yùn)用都已經(jīng)給出了。如果想了解證明的可以參考 勒讓德的三平方定理(維基百科你懂得)

總結(jié)

算法學(xué)到最后主要還是思維，這句話真的沒錯(cuò)，數(shù)學(xué)通過(guò)定理的證明和使用就達(dá)到了使用普通算法達(dá)不到的時(shí)間復(fù)雜度，太讓人佩服了，通過(guò)這道題也算是淺薄的了解了三平方定理和拉格朗日平方和定理，收獲蠻多。
如果文章有寫的不正確的地方還請(qǐng)指出。感恩相遇~