力扣279——完全平方数

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

原题

给定正整数 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的情况,因此你需要看情况选择合适的方法。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题目主要还是在于利用广度优先搜索实现动态规划,也可以找规律,本质其实都是动态规划。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

力扣279——完全平方数

力扣279——完全平方数

上一篇:[动态规划] leetcode 279 Perfect Squares


下一篇:279 - Perfect Squares