leetcode題解279-完全平方數

問題描述

給定正整數 n，找到若幹個完全平方數（比如 1, 4, 9, 16, …）使得它們的和等于 n。你需要讓組成和的完全平方數的個數最少。

給你一個整數 n ，傳回和為 n 的完全平方數的 最少數量 。

完全平方數 是一個整數，其值等于另一個整數的平方；換句話說，其值等于一個整數自乘的積。例如，1、4、9 和 16 都是完全平方數，而 3 和 11 不是。

示例 1：

輸入：n = 12
輸出：3 
解釋：12 = 4 + 4 + 4
           

示例 2：

輸入：n = 13
輸出：2
解釋：13 = 4 + 9
           

提示：

解題思路：

這個問題和斐波那契數問題類似。和斐波那契數一樣，我們可以用更有效的方法來計算解，而不是簡單的遞歸。

解決遞歸中堆棧溢出的問題的一個思路就是使用動态規劃（DP）技術，該技術建立在重用中間解的結果來計算終解的思想之上。

要計算 numSquares(n) 的值，首先要計算 n之前的所有值，即numSquares(n-k) ，這裡k是平方數，如果我們已經在某個地方保留了數字 n-k的解，那麼就不需要使用遞歸計算。

首先初始化長度為 n+1 的數組 dp，每個位置都為 0

如果 n 為 0，則結果為 0

對數組進行周遊，下标為 i，每次都将目前數字先更新為最大的結果，即 dp[i]=i，比如 i=4，最壞結果為 4=1+1+1+1 即為 4 個數字

動态轉移方程為：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i 表示目前數字，jj 表示平方數

時間複雜度：O(nsqrt(n))O(n∗sqrt(n))，sqrt 為平方根

實作代碼

class Solution {
    public int numSquares(int n) {
        //dp[i]代表數i的完全平方數的最少數量
        int dp[]=new int[n+1];
        for(int i=1;i<=n;i++){
            //初始化為i,最壞情況下的完全平方數的個數
            dp[i]=i;
            for(int j=0;i-j*j>=0;j++){
                //比較目前統計的完全平方數的個數，與數i-j*j+j*j這種情況下的完全平方數的個數
                dp[i]=Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}