Question

【279】完全平方数

Answer 1

示例1：

示例2：

动态规划
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
而这个题求正整数n，我们可以运用动态规划的思想，从1开始，求出直到n的个数最少的完全平方和。
首先声明一个n+1大小的数组dp，那么dp[i]就代表数字i所需的最少完全平方数个数，dp[i]初值设为i，即最差情况就是i个1相加。
声明变量j，j * j就代表平方数，如果dp[i-j * j]+1的个数比dp[i]小，那么dp[i]就设为dp[i-j * j]+1，这里+1的原因是j * j本身也要算一个数。

BFS广度优先搜索
当每一次都可以判断出多种情况，有多次的时候就适合用BFS-广度优先遍历
使用BFS应注意：
队列：用来存储每一轮遍历得到的节点；
标记：对于遍历过的节点，应该将它标记，防止重复遍历。
我们将它第一个平方数可能出现的情况做分析 只要 i * i < n 就行
再在此基础上进行二次可能出现的平方数分析
注意：为了节省遍历的时间，曾经（ n - 以前出现的平方数） 这个值出现过，则在此出现这样的数时直接忽略。

看到评论里这个思路的时候，默默感叹吃了没文化的亏，评论里给出了一个数学定理，没仔细研究，有兴趣可以看看
四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。 推论：满足四数平方和定理的数n（四个整数的情况），必定满足 n=4^a(8b+7)