力扣279——完全平方数

jianjianqq 2020-01-11 我要评论

这道题主要利用广度优先搜索进行动态规划，就可以解决了，也可以推导出关系解决。

原题

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

示例 1:

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

示例 2:

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

原题url：https://leetcode-cn.com/problems/perfect-squares/

解题

动态规划 + 广度优先搜索

因为累加的都是完全平方数，这样的组合会有很多种，比如12，可以9 + 1 + 1 + 1或者4 + 4 + 4.，甚至可以12个1相加。那么我们进行在进行动态规划的时候，肯定不是算出所有可能，所以就不是使用深度优先搜索了，因为要求个数最少，那么就自然想到广度优先搜索了。优化的话，自然就是先算最大的数，也就是离 n 最近的且比它小的平方数了。

编码的时候需要注意，一般我们使用队列实现广度优先搜索，因为它是先进先出。

其次，我们需要考虑顺序问题，我们让大的平方数尽量靠前出现，比如上面12 = 9 + 1 + 1 + 1，按照广度优先搜索也会出现12 = 1 + 1 + 1 + 9或者12 = 1 + 9 + 1 + 1等等，后面出现的这些情况理论上都可以直接排除掉，我们可以认为后面那些情况都是第一轮是1之后剩余值为11的衍生，那么都可以合并掉。因此我们又增加一个优化条件：如果曾经出现过的剩余值再次出现，可以不用再次考虑，因为一定会在最开始出现的情况中被考虑到。

接下来我们来看看代码：

import java.util.*;

class Solution {
    public int numSquares(int n) {
        // 利用队列实现广度优先搜索，进行查询。

        TreeNode root = new TreeNode(n, 0);
        // 利用队列进行广度优先搜索
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // 存储已经出现过的剩余值
        boolean record[] = new boolean[n];

        int val, level;
        int i, result;
        while (!queue.isEmpty()) {
            // 移除头节点
            TreeNode node = queue.remove();
            val = node.val;
            level = node.level;
                        // 从最大的平方数开始
            for (i = (int) Math.sqrt(val); i >= 1; i--) {
                result = val - i * i;
                // 剩余值为0，说明可以直接在这一层结束
                if (result == 0) {
                    return level + 1;
                }

                // result如果之前没有出现过，那么就要算上当前的数字，进入下一层中
                if (!record[result]) {
                    record[result] = true;
                    TreeNode nextNode = new TreeNode(result, level + 1);
                    queue.add(nextNode);
                }
            }
        }

        return -1;
    }
}

class TreeNode {
    // 当前节点的值
    int val;
    // 当前属于第几层，也就是当前是第几个数
    int level;

    public TreeNode(int val, int level) {
        this.val = val;
        this.level = level;
    }
}

提交OK。

找规律

还有一种就是利用递推公式了，但可能我数学不好，并没有看懂，给大家看一下：

1. 首先初始化长度为 n+1 的数组dp，每个位置都为0
2. 如果 n 为0，则结果为0
3. 对数组进行遍历，下标为 i，每次都将当前数字先更新为最大的结果，即 dp[i]=i，比如 i=4，最坏结果为 4=1+1+1+1 即为4个数字
4. 动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i表示当前数字，j*j表示平方数

这个思路相当于求出了从1到n所有数字的最小平方数的个数。关键在于第4点，也就是后面的计算可以依赖于前面求出的结果，每一个数都找出其所有基于以前求过的数，加上1个完全平方数后，最小的的平方数的个数。

接下来看看代码：

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) { 
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
            }
        }
        return dp[n];
    }
}

提交OK，但这种方法并没有上面有效率，因为上面可以从最大的平方数找起，只要满足当前n的情况即可，这个的话需要求出所有从1到n的情况，因此你需要看情况选择合适的方法。