279. 完全平方数（BFS）

279. 完全平方数

• 题目
• 解题思路
• 代码

题目

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

解题思路

这题有两种解法，①BFS ②动态规划

1、
这题用BFS解题的关键是如何把题目要求转换成数据结构–“图”。
我们这里用的转换条件是以0作为根节点，它的子节点应该满足 (i*i)+0（poll：被放入到队列中的元素）<=n 注：(1<=i<=n)。

如果满足该要求，那么才可以和0之间有连线。其它的以此类推，来建立起来这个图的模型。
只要建立起模型了，就可以直接套用BFS解题模板了。

2、
这题其实可以看成完全背包问题，完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

dp[i]：和为i的完全平方数的最少数量为dp[i]

主要讲解一下状态转移方程：
dp[j] 可以由dp[j - i ✖️ i]推出， dp[j - i ✖️i] + 1 便可以凑成dp[j]。

此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

代码

class Solution {
      public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.add(0);
        visited.add(0);
        int step = 0;

        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            while (size-- > 0) {
                int poll = queue.poll();
                //一般直接在这里判断poll是否满足目标，满足就直接返回step，但是由于此次判断需要用到变量i，所以把判断是否满足条件放到下面的for循环
                for (int i = 1; i * i + poll <= n; i++) {//寻找该节点周围的节点
                    int target = i * i + poll;//周围的节点应该满足i*i+poll；
                    if (target == n) {
                        return step;
                    }

                    if (target < n && !visited.contains(target)) {
                        queue.add(target);
                        visited.add(target);
                    }

                }
            }
        }
        return -1;
    }
}

---

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // 动态规划数组
        for (int i = 0; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE; // 初始化为最大值
        }
        dp[0] = 0; // 题目给的是非0完全平方数, 因此n = 0时是0种
       
        //外层遍历物品
        for (int i = 1; i * i <= n; i++) { // 每个平方数无限使用, 完全背包
        //内层遍历背包
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1); // 组合累积, 且求的是最少
            }
        }
        return dp[n]; // 返回结果
    }
}