當前位置:網站首頁>力扣 279. 完全平方數

力扣 279. 完全平方數

2022-01-27 17:59:00 冷酷的摸魚小將

題目

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

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

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

示例

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

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

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/perfect-squares
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

方法1:動態規劃

dp[i]:和為 i 的所需完全平方數的最少數量。

Java實現
class Solution {
    
    public int numSquares(int n) {
    
        int[] dp = new int[n + 1];
        if (n == 1) return 1;
        if (n == 2) return 2;
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i < n + 1; i++) {
    
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= Math.sqrt(i); j++) {
    
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min + 1;
        }
        return dp[n];
    }
}

在這裏插入圖片描述

版權聲明
本文為[冷酷的摸魚小將]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271759000306.html

隨機推薦