LeetCode_动态规划_中等_279.完全平方数

深藏阁楼爱情的钟 2023-10-06 22:45 10阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

**示例 1：**  
输入：n = 12  
输出：3  
解释：12 = 4 + 4 + 4

**示例 2：**  
输入：n = 13  
输出：2  
解释：13 = 4 + 9

**提示：**  
1 <= n <= 104

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/perfect-squares

## 2.思路 ##

（1）动态规划  
思路参考[本题官方题解][Link 1]。

相关题目：  
[LeetCode\_动态规划\_中等\_322.零钱兑换][LeetCode_322.]

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public int numSquares(int n) {
        
            // dp[i]:表示和为 n 的完全平方数的最少数量
            int[] dp = new int[n + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            dp[1] = 1;
            for (int i = 1; i <= n; i++) {
        
                for (int j = 1; j * j <= i; j++) {
        
                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
                }
            }
            return dp[n];
        }
    }

[Link 1]: https://leetcode.cn/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode-solut-t99c/
[LeetCode_322.]: https://blog.csdn.net/weixin_43004044/article/details/123103650

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-279.完全平方数

目录题目思路回溯法动态规划动态规划(压缩) 题目来源 [279.完全平方数][279.] 题目思路

柔光的暖阳◎/ 2024年03月25日 20:21/ 0 赞/ 110 阅读

相关 LeetCode_动态规划_中等_279.完全平方数

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个整数 n ，返回和为 n 的完全平方数的最少数量。完全平方数是一个

深藏阁楼爱情的钟/ 2023年10月06日 22:45/ 0 赞/ 11 阅读

相关 Leetcode 279. 完全平方数

Leetcode 279. 完全平方数 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.

墨蓝/ 2023年02月14日 03:06/ 0 赞/ 30 阅读

相关 279. 完全平方数

题目： [279. 完全平方数][279.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

你的名字/ 2022年11月25日 00:58/ 0 赞/ 194 阅读

相关 leetcode 279. Perfect Squares | 279. 完全平方数（动态规划，Java）

题目 [https://leetcode.com/problems/perfect-squares/][https_leetcode.com_problems_perfe

左手的ㄟ右手/ 2022年10月11日 13:50/ 0 赞/ 167 阅读

相关 279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n

心已赠人/ 2022年10月06日 05:42/ 0 赞/ 216 阅读

相关 leetcode279完全平方数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

快来打我*/ 2022年09月03日 12:29/ 0 赞/ 114 阅读

相关 LeetCode 279 完全平方数

https://leetcode-cn.com/problems/perfect-squares/ ![在这里插入图片描述][2f27a9f8cc0b4daeab65061

柔光的暖阳◎/ 2022年09月03日 10:24/ 0 赞/ 212 阅读

相关 leetcode 279 完全平方数

前言题目：[279. 完全平方数][279.] 参考题解：[完全平方数-代码随想录][-] -------------------- 提交代码完全背包问题

刺骨的言语ヽ痛彻心扉/ 2022年08月28日 03:52/ 0 赞/ 194 阅读

相关 LeetCode279——完全平方数

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCod

偏执的太偏执、/ 2022年03月10日 07:24/ 0 赞/ 220 阅读