Nothinginlifeistobefeared.Itisonlytobeunderstood.
生活中没有可畏惧的，只要理解它就能战胜它。
问题描述
给定正整数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遍历像下面这样
他的代码很简单
1publicvoidlevelOrder(TreeNodetree){2QueueTreeNodequeue=newLinkedList();3queue.add(tree);4intlevel=0;//统计有多少层5while(!queue.isEmpty()){6//每一层的节点数7intsize=queue.size();8for(inti=0;isize;i++){9TreeNodenode=queue.poll();10//打印节点11System.out.println(node.val);12if(node.left!=null)13queue.add(node.left);14if(node.right!=null)15queue.add(node.right);16}17level++;18//打印第几层19System.out.println(level);20}21}
我们只需要对他稍作修改就是今天这题的答案了，来看下最终代码
1publicintnumSquares(intn){2QueueIntegerqueue=newLinkedList();3//记录访问过的节点值4SetIntegervisited=newHashSet();5queue.offer(0);6visited.add(0);7//树的第几层8intlevel=0;9while(!queue.isEmpty()){10//每一层的节点数量11intsize=queue.size();12level++;13//遍历当前层的所有节点14for(inti=0;isize;i++){15//节点的值16intdigit=queue.poll();17//访问当前节点的子节点，类比于二叉树的左右子节点18for(intj=1;j=n;j++){19//子节点的值20intnodeValue=digit+j*j;21//nodeValue始终是完全平方数的和，当他等于n的22//时候直接返回23if(nodeValue==n)24returnlevel;25//如果大于n，终止内层循环26if(nodeValuen)27break;28if(!visited.contains(nodeValue)){29queue.offer(nodeValue);30visited.add(nodeValue);31}32}33}34}35returnlevel;36}
动态规划解决
这题除了使用BFS以外，还可以使用动态规划解决。
定义数组dp[]，其中dp表示的是当n等于i的时候完全平方数的最少数量。比如dp[12]表示当n等于12的时候完全平方数的最少数量。这种解法比较类似于背包问题，具体可以看下《，背包问题系列之-基础背包问题》。
比如当n等于60的时候，他的值是dp[60]，但是60还可以由11加上7的平方组成，我们还可以改为dp[11]+1，取最小的即可，即
dp[60]=min(dp[60],dp[11]+1,)
实际上60还可以由24加上6的平方组成……我们只需要找出所有的可能组合并记录最小的值即可。
所以递推公式我们很容易找出来
dp=Math.min(dp,dp[i-j*j]+1);
那么初始条件是什么呢，我们默认任何正整数都是由1的平方组成，即dp=i，也就是最大值，然后再通过递推公式找出最小值即可。
最后我们再来看下代码
1publicintnumSquares(intn){2int[]dp=newint[n+1];3dp[0]=0;4for(inti=1;i=n;i++){5dp=i;//最坏的情况都是由1的平方组成6for(intj=1;j*j=i;j++){7//动态规划公式8dp=Math.min(dp,dp[i-j*j]+1);9}10}11returndp[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个平方数组成了。
我们来看下代码
1publicintnumSquares(intn){2//一，先判断由1个平方数组成的3//如果n是平方数，直接返回1即可，表示n由4//1个平方数组成5if(is_square(n))6return1;7//如果n是4的倍数，就除以4，因为4是2的平方，8//如果n可以由m个完全平方数组成，那么4n也9//可以由m个完全平方数组成10while((n3)==0)11n=2;12//二，在判断由4个平方数组成的13//如果n是4的倍数，在上面代码的执行中就会一直除以4，14//直到不是4的倍数为止，所以这里只需要判断n=(8b+7)15//即可16if((n7)==7)17return4;18intsqrt_n=(int)(Math.sqrt(n));19//三，接着判断由2个平方数组成的20//下面判断是否能由2个平方数组成21for(inti=1;i=sqrt_n;i++){22if(is_square(n-i*i)){23return2;24}25}26//四，剩下的只能由3个平方数组成了27//如果上面都不成立，根据拉格朗日四平方和定理28//只能由3个平方数组成了29return3;30}//判断n是否是平方数33publicbooleanis_square(intn){34intsqrt_n=(int)(Math.sqrt(n));35returnsqrt_n*sqrt_n==n;36}
●，BFS和DFS解二叉树的层序遍历II
●，DFS和BFS解合并二叉树
●，动态规划解按摩师的最长预约时间
●.递归和动态规划解三角形最小路径和
截止到目前我已经写了多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有多页，大家可以在
相信每个人都有过被代码的小bug搞得心态爆炸的经历，本文分享一个我最常用的简单技巧，可以大幅提升刷题的幸福感。
在这之前，首先回答一个问题，刷力扣题是直接在网页上刷比较好还是在本地IDE上刷比较好？
如果是牛客网笔试那种自己处理输入输出的判题形式，一定要在IDE上写，这个没啥说的，但像力扣这种判题形式，我个人偏好直接在网页上刷，原因有二：
1、方便
因为力扣有的数据结构是自定的，比如说TreeNode，ListNode这种，在本地你还得把这个类copy过去。
而且在IDE上没办法测试，写完代码之后还得粘贴到网页上跑测试数据，那还不如直接网页上写呢。
算法又不是工程代码，量都比较小，IDE的自动补全带来的收益基本可以忽略不计。
2、实用
到时候面试的时候，面试官给你出的算法题大都是希望你直接在网页上完成的，最好是边写边讲你的思路。
如果平时练习的时候就习惯没有IDE的自动补全，习惯手写代码大脑编译，到时候面试的时候写代码就能更快更从容。
之前我面快手的时候，有个面试官让我实现LRU算法，我直接把双链表的实现、哈希链表的实现，在网页上全写出来了，而且一次无bug跑通，可以看到面试官惊讶的表情??
我秋招能当offer收割机，很大程度上就是因为手写算法这一关超出面试官的预期，其实都是因为之前在网页上刷题练出来的。
接下来分享我觉得最常实用的干货技巧。
如何给算法debug代码的错误时无法避免的，有时候可能整个思路都错了，有时候可能是某些细节问题，比如i和j写反了，这种问题怎么排查？
我想一般的算法问题肯定不难排查，肉眼检查应该都没啥问题，再不济print打印一些关键变量的值，总能发现问题。
比较让人头疼的的应该是递归算法的问题排查。
如果没有一定的经验，函数递归的过程很难被正确理解，所以这里就重点讲讲如何高效debug递归算法。
有的读者可能会说，把算法copy到IDE里面，然后打断点一步步跟着走不就行了吗？
这个方法肯定是可以的，但是之前的文章多次说过，递归函数最好从一个全局的角度理解，而不要跳进具体的细节。
如果你对递归还不够熟悉，没有一个全局的视角，这种一步步打断点的方式也容易把人绕进去。
我的建议是直接在递归函数内部打印关键值，配合缩进，直观地观察递归函数执行情况。
最能提升我们debug效率的是缩进，除了解法函数，我们新定义一个函数printIndent和一个全局变量count：
//全局变量，记录递归函数的递归层数intcount=0;//输入n，打印n个tab缩进voidprintIndent(intn){for(inti=0;in;i++){printf("");}}
接下来，套路来了：
在递归函数的开头，调用printIndent(count++)并打印关键变量；然后在所有return语句之前调用printIndent(--count)并打印返回值。
举个具体的例子，比如说上篇文章练琴时悟出的一个动态规划算法中实现了一个递归的dp函数，大致的结构如下：
intdp(stringring,inti,stringkey,intj){/*basecase*/if(j==key.size()){return0;}/*状态转移*/intres=INT_MAX;for(intk:charToIndex[key[j]]){res=min(res,dp(ring,j,key,i+1));}returnres;}
这个递归的dp函数在我进行了debug之后，变成了这样：
intcount=0;voidprintIndent(intn){for(inti=0;in;i++){printf("");}}intdp(stringring,inti,stringkey,intj){//printIndent(count++);//printf("i=%d,j=%d\n",i,j);if(j==key.size()){//printIndent(--count);//printf("return0\n");return0;}intres=INT_MAX;for(intk:charToIndex[key[j]]){res=min(res,dp(ring,j,key,i+1));}//printIndent(--count);//printf("return%d\n",res);returnres;}
就是在函数开头和所有return语句对应的地方加上一些打印代码。
如果去掉注释，执行一个测试用例，输出如下：
这样，我们通过对比对应的缩进就能知道每次递归时输入的关键参数i,j的值，以及每次递归调用返回的结果是多少。
最重要的是，这样可以比较直观地看出递归过程，你有没有发现这就是一棵递归树？
前文动态规划套路详解说过，理解递归函数最重要的就是画出递归树，这样打印一下，连递归树都不用自己画了，而且还能清晰地看出每次递归的返回值。
可以说，这是对刷题「幸福感」提升最大的一个小技巧，比IDE打断点要高效。
好了，本文分享就到这里，马上快过年了，估计大家都无心学习了，不过刷题还是要坚持的，这就叫弯道超车，顺便实践一下这个技巧。
如果本文对你有帮助，点个在看，就会被推荐更多相似文章。
推荐阅读：
完全整理
篇高质技术文章目录整理
算法之美:栈和队列
主宰这个世界的10大算法
彻底理解cookie、session、token
浅谈什么是递归算法
专注服务器后台技术栈知识总结分享
欢迎
?扫码免费试看专栏
这个专栏最大的优势就是专注于算法面试场景，（面试是我们谁都无法逃避的问题，不论是求职还是晋升。）数据结构和算法五花八门，有些你根本不需要花费大量的时间和精力去准备，有些甚至看都不用看。我看中这门课一个比较核心的目的，就是可以有的放矢地准备面试，知道哪些数据结构和算法是常考的，哪些是必须花时间好好准备的。苏勇在力扣（LeetCode）上千道题目中，筛选了30道有代表性的考题，15道面试官高频考题。涵盖了面试中绝大部分的基础知识和算法，而且都是面试实战中必须要牢牢掌握好的。有难度较低的数组、链表、栈、队列，也有递归、深度、广度优先搜索等比较难以掌握的内容。课里的代码，都通过了力扣（LeetCode）平台的测试，都是比较精简的实现，剔除冗余和复杂的逻辑，帮你用最简单的方式，体现解题的思路。让你在最短的时间里准确地把握住面试准备的方向，有的放矢地学习应该要掌握好的数据结构和算法。从最暴力的方式开始，一步步地将你引导到最佳的解法，课程中有丰富的动画，让你在学习枯燥的数据结构和算法中，准确地体会到解题的精髓所在。适合谁学？如果你是刚刚毕业的学生，无论是计算机专业科班出身还是其他专业，这门课程能帮助你掌握好数据结构和算法的基础，同时，通过力扣平台，能让你尽快地融入到找工作的状态。如果你有了一定的工作经验并想找到更具挑战的大厂，那么这门课程能帮助你在分析问题的时候，从最基本的暴力法开始，一步步地学习到如何想出最佳的办法，达到大厂的面试水准。无论你是前端工程师，后端工程师还是全栈工程师，在面试的时候，都必须要准确地分析出算法的时间复杂度和空间复杂度，在这门课里，有专门介绍分析复杂度的环节，尤其是对递归算法的复杂度分析，相信一定能帮助到你。专栏已经全部更新完毕，不论你是准备面试突击使用，还是先储备知识，留作之后面试都十分合适。限时福利看在我的真心推荐上，拉勾给了我们一些限时福利：原价￥98，限时优惠￥68，接近6折的优惠（仅限24小时）；
订阅后，点击「阅读原文」，凭购买截图可免费进入“算法交流群”。
如何订阅？扫描下图