279. 完全平方数——（LeetCode刷题）-蒲公英云

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

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 的最短路径。
本题也可以用动态规划求解，在之后动态规划部分中会再次出现。

法二：动态规划

可以将此题理解为完全背包问题。

状态转移方程为：
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;
    }
}