531，BFS和动态规划解完全平方数
Nothing in life is to be feared. It is only to be understood.
生活中没有可畏惧的，只要理解它就能战胜它。
问题描述
给定正整数n，找到若干个完全平方数（比如1，4，9，16,...）使得它们的和等于n。你需要让组成和的完全平方数的个数最少。
给你一个整数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 <= 10^4
BFS解决
这题让求的是若干个平方数的和等于n，并且平方数的个数最少。首先我们可以把它想象成为一颗m叉树，树的每一个节点的值都是平方数的和，如下图所示。
每一个节点的值都是从根节点到当前节点的累加。而平方数的个数其实就是遍历到第几层的时候累加和等于target。我们只需要一层一层的遍历，也就是常说的BFS，当遇到累加的和等于target的时候直接返回当前的层数即可。
二叉树的BFS遍历像下面这样
他的代码很简单
1public void levelOrder(TreeNode tree) {
2 Queue<TreeNode> queue = new LinkedList<>();
3 queue.add(tree);
4 int level = 0;//统计有多少层
5 while (!queue.isEmpty()) {
6 //每一层的节点数
7 int size = queue.size();
8 for (int i = 0; i < size; i++) {
9 TreeNode node = queue.poll();
10 //打印节点
11 System.out.println(node.val);
12 if (node.left != null)
13 queue.add(node.left);
14 if (node.right != null)
15 queue.add(node.right);
16 }
17 level++;
18 //打印第几层
19 System.out.println(level);
20 }
21}
我们只需要对他稍作修改就是今天这题的答案了，来看下最终代码
1public int numSquares(int n) {
2 Queue<Integer> queue = new LinkedList<>();
3 //记录访问过的节点值
4 Set<Integer> visited = new HashSet<>();
5 queue.offer(0);
6 visited.add(0);
7 //树的第几层
8 int level = 0;
9 while (!queue.isEmpty()) {
10 //每一层的节点数量
11 int size = queue.size();
12 level++;
13 //遍历当前层的所有节点
14 for (int i = 0; i < size; i++) {
15 //节点的值
16 int digit = queue.poll();
17 //访问当前节点的子节点，类比于二叉树的左右子节点
18 for (int j = 1; j <= n; j++) {
19 //子节点的值
20 int nodeValue = digit + j * j;
21 //nodeValue始终是完全平方数的和，当他等于n的
22 //时候直接返回
23 if (nodeValue == n)
24 return level;
25 //如果大于n，终止内层循环
26 if (nodeValue > n)
27 break;
28 if (!visited.contains(nodeValue)) {
29 queue.offer(nodeValue);
30 visited.add(nodeValue);
31 }
32 }
33 }
34 }
35 return level;
36}
动态规划解决
这题除了使用BFS以外，还可以使用动态规划解决。
定义数组dp[]，其中dp[i]表示的是当n等于i的时候完全平方数的最少数量。比如dp[12]表示当n等于12的时候完全平方数的最少数量。这种解法比较类似于背包问题，具体可以看下《371，背包问题系列之-基础背包问题》。
比如当n等于60的时候，他的值是dp[60]，但是60还可以由11加上7的平方组成，我们还可以改为dp[11]+1，取最小的即可，即
dp[60]=min(dp[60],dp[11]+1,)
实际上60还可以由24加上6的平方组成……我们只需要找出所有的可能组合并记录最小的值即可。
所以递推公式我们很容易找出来
dp[i]=Math.min(dp[i],dp[i-j*j]+1);
那么初始条件是什么呢，我们默认任何正整数都是由1的平方组成，即dp[i]=i，也就是最大值，然后再通过递推公式找出最小值即可。
最后我们再来看下代码
1public int numSquares(int n) {
2 int[] dp = new int[n + 1];
3 dp[0] = 0;
4 for (int i = 1; i <= n; i++) {
5 dp[i] = i;//最坏的情况都是由1的平方组成
6 for (int j = 1; j * j <= i; j++) {
7 //动态规划公式
8 dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
9 }
10 }
11 return dp[n];
12}
拉格朗日四平方和定理
拉格朗日四平方和定理说明任何一个数，都可以由小于等于4个的完全平方数相加得到。
当n=(8b+7)*4^n的时候，n是由4个完全平方数得到，否则n只能由1个，2个或者3个完全平方数得到。
由1个，2个和4个完全平方数得到的n我们很容易判断，所以剩下的就是由3个完全平方数得到的n。我们分为4步走的战略，
先判断是否能由1个平方数组成
在判断是否能由4个平方数组成
接着判断是否能由2个平方数组成
如果上面都不成立，只能由3个平方数组成了。
我们来看下代码
1public int numSquares(int n) {
2 //一，先判断由1个平方数组成的
3 //如果n是平方数，直接返回1即可，表示n由
4 //1个平方数组成
5 if (is_square(n))
6 return 1;
7 //如果n是4的倍数，就除以4，因为4是2的平方，
8 //如果n可以由m个完全平方数组成，那么4n也
9 //可以由m个完全平方数组成
10 while ((n & 3) == 0)
11 n >>= 2;
12 //二，在判断由4个平方数组成的
13 //如果n是4的倍数，在上面代码的执行中就会一直除以4，
14 //直到不是4的倍数为止，所以这里只需要判断n=(8b+7)
15 //即可
16 if ((n & 7) == 7)
17 return 4;
18 int sqrt_n = (int) (Math.sqrt(n));
19 //三，接着判断由2个平方数组成的
20 //下面判断是否能由2个平方数组成
21 for (int i = 1; i <= sqrt_n; i++) {
22 if (is_square(n - i * i)) {
23 return 2;
24 }
25 }
26 //四，剩下的只能由3个平方数组成了
27 //如果上面都不成立，根据拉格朗日四平方和定理
28 //只能由3个平方数组成了
29 return 3;
30}
31
32//判断n是否是平方数
33public boolean is_square(int n) {
34 int sqrt_n = (int) (Math.sqrt(n));
35 return sqrt_n * sqrt_n == n;
36}
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有900多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。