求给定数等于最少的几个完全平方数之和

大家好，这道题目要求求最少的几个完全平方数之和等于某个数，我在网上找了一些答案，都是用递归暴力求解，我可以证明
（N+1）^2 > 1 + 2^2 + 3^2 + ... + n^2,
根据这样的证明式子，我觉得可以直接用贪心，每一步都求最大可以给定的数，直到满足结果为止，这样的结果我觉得应该就是最短的，不知道我的想法正确与否。

给出一个参考链接，用的就是递归暴力求解，我觉得贪心应该也没问题啊。
http://www.cnphp6.com/archives/63224

可以继续rogerdai说的方法, 但是用更多的数论定理...
4. Lagrange's four-square theorem就不用暴力最后一种可能.
3. Legendre's three-square theorem可以保证可以被写成3个square的版本也可以高效的解决. 只需要不断的除4再检测剩下的数字-7是否可以被8整除
2. Fermat's two square theorem让两个square的版本变成factorization问题.
1. 一个square变成检测数字是否是个square.
现有的技术的bottleneck是第二部分, 需要factorize整数. 可以得到O(n^ɛ)的算法对于任意小常数ɛ>0.
虽然...对于1,2两个问题直接创建O(sqrt(n))的表比较方便... 从而获得O(sqrt(n))的算法...

今天google面试碰到了这个题，应该是bar raiser，
可以用一个hashmap<Integer,List<Integer>> 来保留中间结果，
如果知道最大不会超过4的话，可以考虑用下面的优化：
<0,{}>
然后把所有比N小的平方和先put到这个map里
<1, {1}>
<4,{2}>
<9,{3}>
...
如果想要更优的话，把两个平方和也放进去
<2, {1,1}>
<5, {1,2}>
....
之后带着这个map递归

对于每个n，如果map.containsKey(n)，直接返回map.get(n)
否则 for (i = sqrt(n); i>= 1; i--)  {  找到最小的 min(（1 + size(find(n - i *i)))）)}
...

qieguo 发表于 2015-8-3 15:15
我在想贪心为什么不对呢？我试着举例发现贪心结果没错 但是也没办法去验证

可以参考 http://stackoverflow.com/questio ... -for-some-coin-sets

But for some coin sets, there are sums for which the greedy algorithm fails. For example, for the set {1, 15, 25} and the sum 30, the greedy algorithm first chooses 25, leaving a remainder of 5, and then five 1s for a total of six coins. But the solution with the minimal number of coins is to choose 15 twice.

这个有两种解法：
第一种是DP，先在O(sqrt(n))时间找出所有平方数因子，然后用coin change找出最少
组合。
第二种是深搜，也是先在O(sqrt(n))时间找出所有平方数因子，然后就暴力深搜，但是
深搜的最大深度是3，如果都搜不到就返回4. (拉格朗日平方数和定理) 当然在深搜过程中可以记下最短的路径。

rogerdai 发表于 2015-8-3 13:48
这个有两种解法：
第一种是DP，先在O(sqrt(n))时间找出所有平方数因子，然后用coin change找出最少
组合 ...

我在想贪心为什么不对呢？我试着举例发现贪心结果没错 但是也没办法去验证

这链接是楼主自己的博客吗？题目原链接能给个吗？这个没说清楚题意，平方数必须连续吗？是从1开始吗？

如果平方数不用从1开始，也不要求连续，而且要求加起来等于target的话，那应该就是DP最方便了。
而且可以一口气算好，之后直接打表就行了。

qieguo 发表于 2015-8-3 15:15
我在想贪心为什么不对呢？我试着举例发现贪心结果没错 但是也没办法去验证

每次都取最大的话，比如12会取成9+1+1+1
但更短的组合是12=4+4+4
这么一来总的DP复杂度应该是O(N ^ 1.5)

zhuli19901106 发表于 2015-8-3 22:31
每次都取最大的话，比如12会取成9+1+1+1
但更短的组合是12=4+4+4
这么一来总的DP复杂度应该是O(N ^ 1.5 ...

可是我不太明白 DP 应该怎么取转移方程呢 我没怎么看懂上面写的 谢谢

zhuli19901106 发表于 2015-8-3 22:23
这链接是楼主自己的博客吗？题目原链接能给个吗？这个没说清楚题意，平方数必须连续吗？是从1开始吗？

PS 这个链接不是我 是我从网上找到的题目

qieguo 发表于 2015-8-3 23:10
可是我不太明白 DP 应该怎么取转移方程呢 我没怎么看懂上面写的 谢谢

给定一个N，那么DP{N} = min(DP{N - i * i} + 1)，其中N - i*i >= 0，i取遍所有可能的值。所以求出每个值需要O(sqrt(N))的时间。总时间复杂度就是O(N * sqrt(N))。
DP{0} = 0
DP{N}代表N分解成平方数之和的最短长度。