279. 完全平方数

你的名字 2022-11-25 00:58 171阅读 0赞

# 题目： #

[279. 完全平方数][279.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

## 1. 题解一：数学运算 ##

![在这里插入图片描述][20200807002312102.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]

## 2. 题解二：动态规划 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]

n = 12
    先把 n 减去一个平方数，然后求剩下的数分解成平方数和所需的最小个数
    
    把 n 减去 1, 然后求出 11 分解成平方数和所需的最小个数,记做 n1
    那么当前方案总共需要 n1 + 1 个平方数
    
    把 n 减去 4, 然后求出 8 分解成平方数和所需的最小个数,记做 n2
    那么当前方案总共需要 n2 + 1 个平方数
    
    把 n 减去 9, 然后求出 3 分解成平方数和所需的最小个数,记做 n3
    那么当前方案总共需要 n3 + 1 个平方数
    
    下一个平方数是 16, 大于 12, 不能再分了。
    
    接下来我们只需要从 (n1 + 1), (n2 + 1), (n3 + 1) 三种方案中选择最小的个数, 
    此时就是 12 分解成平方数和所需的最小个数了
    
    至于求 11、8、3 分解成最小平方数和所需的最小个数继续用上边的方法去求
    
    直到如果求 0 分解成最小平方数的和的个数, 返回 0 即可

# 代码： #

## 1. 代码一：数学运算 ##

import java.util.*;
    
    public class code279 { 
        
        // 判断是否是[完全]平方数
        public static boolean isSquare(int n) 
        { 
            int sqrt = (int) Math.sqrt(n);
            return sqrt * sqrt == n;
        }
        
        public static int numSquares(int n) 
        { 
            // 判断答案是否是 1
            if(isSquare(n))
            { 
                return 1;
            }
    
            // 判断答案是否是 4
            int temp = n;
            while(temp % 4 == 0)
            { 
                temp /= 4;
            }
            if(temp % 8 == 7)
            { 
                return 4;
            }
    
            // 判断答案是否是 2
            for(int i = 1; i * i <= n; i++)
            { 
                if(isSquare(n - i * i))
                { 
                    return 2;
                }
            }
            // 以上情况都排除的话，答案就是 3
            return 3;
        }
        
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNextInt()) 
            { 
                int n = sc.nextInt();
                int res = numSquares(n);
                System.out.println(res);
            }        
        }
    }

## 2. 代码二：动态规划 ##

import java.util.*;
    
    public class code279 { 
    
        // 方法2：动态规划
        public static int numSquares(int n) { 
            // dp[i]表示 i 最少可以由几个[完全]平方数构成
            int dp[] = new int[n + 1]; // 默认初始化值都为0
            dp[0] = 0;
            for(int i = 1; i <= n; i++)
            { 
                dp[i] = i; // 最坏的情况就是每次+1
            }        
            // 依次求出 1, 2... 直到 n 的解
            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];
        }
        
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNextInt()) 
            { 
                int n = sc.nextInt();
                int res = numSquares(n);
                System.out.println(res);
            }        
        }
    }

# 参考： #

1.  [详细通俗的思路分析，多解法][Link 1]
2.  [完全平方数][Link 2]
3.  [画解算法：279. 完全平方数][279. 1]
4.  [python3最基础的BFS套路代码，适合入门新手！][python3_BFS]
5.  [【超直白】【靠嘴讲】小学生都能看懂的题解，还看不懂我打你~][Link 3]
6.  [动态规划+BFS 逐行解释 python3][BFS _ python3]
7.  [不只是答案，而是动态规划类题的思考过程][Link 4]
8.  [Java 解法：将问题转化为图论][Java]

# 附： #

递归、记忆化搜索、动态规划之间的联系：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 7]

[279.]: https://leetcode-cn.com/problems/perfect-squares/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20221124/8f41f40fb0f04e22a4a04930f8bcfd33.png
[20200807002312102.png]: /images/20221124/abbd0594dcde433c9dad0a71ec572130.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: /images/20221124/f7f2eace24dc460b8736dc3be60cde58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: /images/20221124/7d22ab2301c247b784a48d14e6a6433b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: /images/20221124/2c8a85e043ff451490cc09a339d5f9ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: /images/20221124/79054db056d441e2960fe7e47ce2ebf9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]: /images/20221124/6805a08dd5df4d72bc00974be5e2eb4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]: /images/20221124/07bfb7f317334f8287fc2ee95c2850b9.png
[Link 1]: https://leetcode-cn.com/problems/perfect-squares/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--51/
[Link 2]: https://leetcode-cn.com/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode/
[279. 1]: https://leetcode-cn.com/problems/perfect-squares/solution/hua-jie-suan-fa-279-wan-quan-ping-fang-shu-by-guan/
[python3_BFS]: https://leetcode-cn.com/problems/perfect-squares/solution/python3zui-ji-chu-de-bfstao-lu-dai-ma-gua-he-ru-me/
[Link 3]: https://leetcode-cn.com/problems/perfect-squares/solution/chao-zhi-bai-kao-zui-jiang-xiao-xue-sheng-du-neng-/
[BFS _ python3]: https://leetcode-cn.com/problems/perfect-squares/solution/dong-tai-gui-hua-bfs-zhu-xing-jie-shi-python3-by-2/
[Link 4]: https://leetcode-cn.com/problems/perfect-squares/solution/bu-zhi-shi-da-an-er-shi-dong-tai-gui-hua-lei-ti-de/
[Java]: https://leetcode-cn.com/problems/perfect-squares/solution/java-jie-fa-jiang-wen-ti-zhuan-hua-wei-tu-lun-by-b/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 7]: /images/20221124/6235eb52c050400c84c16af8e979fc2a.png