LeetCode：279. Perfect Squares（完美的平方）

布满荆棘的人生 2022-04-03 08:43 174阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方法1：动态规划

python实现方法1：

源码github地址：https://github.com/zhangyu345293721/leetcode

--------------------

### 题目描述： ###

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

示例 1:

输入: n = 12
    输出: 3 
    解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13
    输出: 2
    解释: 13 = 4 + 9

来源：力扣（LeetCode）

--------------------

### java实现方法1：动态规划 ###

/**
         * 最少完全平方组成
         *
         * @param n 输入数字
         * @return 多少数组成
         */
        public int numSquares(int n) {
            int[] dp = new int[n + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            for (int i = 0; i * i <= n; i++) {
                dp[i * i] = 1;
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j * j <= i; j++) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - j * j]);
                }
            }
            return dp[n];
        }

时间复杂度:O(n^2)

空间复杂度:O(n)

--------------------

### python实现方法1： ###

import sys
    
    
    def num_squares(self, n: int) -> int:
        '''
            找出一个数是平方的和
        Args:
            num: 数字
        Returns:
            数字和
        '''
        dp = [sys.maxsize] * (n + 1)
        dp[0] = 0
        i = 1
        while i * i <= n:
            dp[i * i] = 1
            i += 1
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], 1 + dp[i - j * j])
                j += 1
        return dp[n]

时间复杂度:O(n^2)

空间复杂度:O(n)

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode