一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 603|回复: 11
收起左侧

[算法题] 求给定数等于最少的几个完全平方数之和

[复制链接] |试试Instant~ |关注本帖
qieguo 发表于 2015-8-3 13:31:05 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

给出一个参考链接,用的就是递归暴力求解,我觉得贪心应该也没问题啊。
http://www.cnphp6.com/archives/63224
rogerdai 发表于 2015-8-3 13:48:36 | 显示全部楼层
这个有两种解法:
第一种是DP,先在O(sqrt(n))时间找出所有平方数因子,然后用coin change找出最少
组合。
第二种是深搜,也是先在O(sqrt(n))时间找出所有平方数因子,然后就暴力深搜,但是
深搜的最大深度是3,如果都搜不到就返回4. (拉格朗日平方数和定理) 当然在深搜过程中可以记下最短的路径。
回复 支持 反对

使用道具 举报

 楼主| qieguo 发表于 2015-8-3 15:15:25 | 显示全部楼层
rogerdai 发表于 2015-8-3 13:48
这个有两种解法:
第一种是DP,先在O(sqrt(n))时间找出所有平方数因子,然后用coin change找出最少
组合 ...

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

使用道具 举报

zhuli19901106 发表于 2015-8-3 22:23:52 | 显示全部楼层
这链接是楼主自己的博客吗?题目原链接能给个吗?这个没说清楚题意,平方数必须连续吗?是从1开始吗?
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-8-3 22:28:32 | 显示全部楼层
如果平方数不用从1开始,也不要求连续,而且要求加起来等于target的话,那应该就是DP最方便了。
而且可以一口气算好,之后直接打表就行了。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-8-3 22:31:37 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-8-3 22:32 编辑
qieguo 发表于 2015-8-3 15:15
我在想贪心为什么不对呢?我试着举例发现贪心结果没错 但是也没办法去验证

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

使用道具 举报

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

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

使用道具 举报

 楼主| qieguo 发表于 2015-8-3 23:11:11 | 显示全部楼层
zhuli19901106 发表于 2015-8-3 22:23
这链接是楼主自己的博客吗?题目原链接能给个吗?这个没说清楚题意,平方数必须连续吗?是从1开始吗?

PS 这个链接不是我 是我从网上找到的题目
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-8-3 23:33:19 | 显示全部楼层
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分解成平方数之和的最短长度。
回复 支持 反对

使用道具 举报

mgccl 发表于 2015-8-4 00:14:18 | 显示全部楼层
可以继续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))的算法...
回复 支持 反对

使用道具 举报

rogerdai 发表于 2015-8-5 13:36:37 | 显示全部楼层
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.
回复 支持 反对

使用道具 举报

wsmjmiisme 发表于 2015-9-22 04:06:42 | 显示全部楼层
今天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)))))}
...
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 23:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表