这道题主要利用广度优先搜索进行动态规划,就可以解决了,也可以推导出关系解决。
原题
给定正整数 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的情况,因此你需要看情况选择合适的方法。
总结
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题目主要还是在于利用广度优先搜索实现动态规划,也可以找规律,本质其实都是动态规划。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。
公众号:健程之道