279. 完全平方数——（LeetCode刷题）

柔光的暖阳◎ 2024-04-01 19:46 61阅读 0赞

### 279. 完全平方数 ###

给你一个整数 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 < = 1 0 4 1 <= n <= 10^4 1<=n<=104

#### 思路： ####

**法一**：**（BFS）**

*  可以将每个整数看成图中的一个节点，如果两个整数之差为一个平方数，那么这两个整数所在的节点就有一条边。
 *  要求解最小的平方数数量，就是求解从节点 n 到节点 0 的最短路径。
 *  本题也可以用动态规划求解，在之后动态规划部分中会再次出现。

**法二：动态规划**

可以将此题理解为[完全背包][Link 1]问题。

*  状态转移方程为：  
     d p \[ j \] = min ⁡ ( d p \[ j \] , d p \[ j − s q u a r e \] + 1 ) dp\[j\]=\\min (dp\[j\], dp\[j-square\]+1) dp\[j\]=min(dp\[j\],dp\[j−square\]\+1)

#### 代码：（Java） ####

**法一**：**（BFS）**

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    public class bfs_per_squar {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int n = 12;
    		System.out.println(numSquares(n));
    	}
    	public static int numSquares(int n) {
        
    		List<Integer> squares = generateSquares(n);
    		Queue<Integer> queue = new LinkedList<>();
    		boolean[] marked = new boolean[n + 1];
    		queue.add(n);
    		marked[n] = true;
    		int level = 0;
    		while (!queue.isEmpty()) {
        
    			int size = queue.size();
    			level++;
    			while(size-- > 0) {
        
    				int cur = queue.poll();
    				for(int s : squares) {
        
    					int next = cur - s;
    					if(next < 0) {
        
    						break;
    					}
    					if(next == 0) {
        
    						return level;
    					}
    					if(marked[next]) {
        
    						continue;
    					}
    					marked[next] = true;
    					queue.add(next);
    				}
    			}
    		}
    		return n;
    	}
    	private static List<Integer> generateSquares(int n) {
        
    		// TODO 自动生成的方法存根
    		List<Integer> squares = new ArrayList<>();
    		for(int i = 1; i <= (int)Math.sqrt(n); i++) {
        
    			squares.add(i*i);
    		}
    		return squares;
    	}
    }

**法二：动态规划**

import java.util.ArrayList;
    import java.util.List;
    
    public class PerfectSquares {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int n = 12;
    		System.out.println(numSquares(n));
    	}
    	public static int numSquares(int n) {
        
    		List<Integer> squares = generateSquares(n);
    		int []dp = new int[n + 1];
    		for(int j = 1; j <= n; j++) {
        
    			int min = Integer.MAX_VALUE;
    			for(int square : squares) {
        
    				if(square > j) break;
    				min = Math.min(min, dp[j - square] + 1);
    			}
    			dp[j] = min;
    		}
    		return dp[n];
    	}
    	public static List<Integer> generateSquares(int n){
        
    		List<Integer> squares = new ArrayList<>();
    		for(int i = 1; i <= (int)Math.sqrt(n); i++) {
        
    			squares.add(i * i);
    		}
    		return squares;
    	}
    }

#### 输出： ####

![在这里插入图片描述][5be57a139dfe47fb8859e2ee8815f38d.png]

##### 复杂度分析：(法二) #####

时间复杂度：共有  n ∗ n n ∗ \\sqrt\{n\} n∗n 个状态需要转移，复杂度为  n ∗ n n \* \\sqrt\{n\} n∗n。  
空间复杂度：O(n)。

##### 注：仅供学习参考 #####

来源：[力扣][Link 2]

[Link 1]: https://blog.csdn.net/weixin_46503238/article/details/115096267?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167828070616800180658767%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167828070616800180658767&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-115096267-null-null.142%5Ev73%5Econtrol,201%5Ev4%5Eadd_ask,239%5Ev2%5Einsert_chatgpt&utm_term=%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85&spm=1018.2226.3001.4187
[5be57a139dfe47fb8859e2ee8815f38d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/360a606be9d541829b0e0076e28eb3b5.png
[Link 2]: https://leetcode.cn/problems/perfect-squares/description/