如何解決leetcode中完全平方數的問題

發布時間：2022-01-17 13:37:37 來源：億速云閱讀：143 作者：小新欄目：大數據

這篇文章主要為大家展示了“如何解決leetcode中完全平方數的問題”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“如何解決leetcode中完全平方數的問題”這篇文章吧。

題目鏈接

https://leetcode-cn.com/problems/perfect-squares/

題目描述

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

示例 1:

輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4.

示例 2:

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

解題方案

思路

標簽：動態規劃
首先初始化長度為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表示當前數字，j*j表示平方數
時間復雜度：O(n*sqrt(n))，sqrt為平方根

代碼

Java版本

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // 默認初始化值都為0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最壞的情況就是每次+1
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 動態轉移方程
            }
        }
        return dp[n];
    }
}

JavaScript版本

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    const dp = [...Array(n+1)].map(_=>0); // 數組長度為n+1，值均為0
    for (let i = 1; i <= n; i++) {
        dp[i] = i; // 最壞的情況就是每次+1
        for (let j = 1; i - j * j >= 0; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 動態轉移方程
        }
    }
    return dp[n];
};