问一道最简单的题把一个数拆成任意个平方和的最小拆法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道最简单的题把一个数拆成任意个平方和的最小拆法

问一道最简单的题把一个数拆成任意个平方和的最小拆法# JobHunting - 待字闺中

b*u2015-08-01 07:08

1 楼

婆婆年纪大了，我老公就说接过来好了，我肯定是没有意见的。婆媳关系上的话，我
自认为和婆婆相处的不错，绝对是一个好媳妇。
前几个月相处的还算不错，最近婆婆总是在我洗澡的时候上厕所。我一般洗澡的话不
会拉浴帘，每次我洗澡的时候都特意问一下婆婆要不要上厕所，她每次都说不上。可每
次我洗到一半的时候直接推门进来了，连个门都不敲，真的让我挺反感的，心里很是生
气。
婆婆要是真的着急的话最起码可以敲一下门呀，好让我有个心里准备，每次都吓得我要
死。洗澡的时候我真的不喜欢拉浴帘，心里有不好的阴影，一直挺害怕的。都是女的没
有什么，婆婆也是长辈，可我心里不舒服呀，感觉完全没有尊重我，有点侵犯我的隐私
了，总是挑我洗澡的时候上厕所，婆婆真的没有其他想法吗？每次只是碰巧，可次数多
的数不清了。
我是不能和老公说这件事情，要是说了感觉我就是在挑事儿的人，可我心里也很委屈
，有种被侵犯的感觉，洗个澡都不能好好洗了，生怕我婆婆会突然进来，婆婆是完全没
有意识到这个呀。我真的自认自己是很懂事的媳妇，可我真的觉得婆婆有点过分了，也
不知道她心里是怎么想的，完全就是炒鸡不方便呀，求婆婆不要在我洗澡的时候上厕所
了。

f*52015-08-01 07:08

2 楼

我的想法是贪心，每次找出最大的再减去，不过总感觉不对，请问正确的做法是？

b*m2015-08-01 07:08

3 楼

这是算法题吗？
一个一个试吧。
先把所有比这个数小的平方数找出来，看看能不能写成2个的和。
不行，就看看能不能写成3个的。。。
手算的话应该没什么好办法。

r*y2015-08-01 07:08

4 楼

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

f*52015-08-01 07:08

5 楼

想法非常好！感谢

【在 r******y 的大作中提到】

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

T*u2015-08-01 07:08

6 楼

s*m2015-08-01 07:08

7 楼

人要的是“最小拆法”，不是“4”

【在 r******y 的大作中提到】

s*a2015-08-01 07:08

8 楼

最多只需要四个就行所以你写个循环都好

w*n2015-08-01 07:08

9 楼

背包dp吧。

j*22015-08-01 07:08

10 楼

请问 1 可以成为组成部分么？如果不可以的话应该有些情况没有解如果可以有1 的
话贪心可以做吧
如果可以的话
我觉得可以
while(n != 0) {
m = Math.sqrt(n);
result.add(m);
n = n - m * m;
}
假设输入是n = 14
第一次存进的是3
n = 14 - 9 = 5
第二次存进是2
n = 5 - 4 = 1
第三次存进是1
n = 1 - 1 = 0
结果是3， 2， 1
假设输入时n 是平方数则结果就是开方
如果不能为1，可参照2l大哥的解法，但是dp逻辑很复杂， dfs会非常慢

b*m2015-08-01 07:08

11 楼

不是要求最小拆法吗？
要是48按你这算法就不是最小了。
楼上说的dp是啥？不懂呀。

【在 j********2 的大作中提到】

: 请问 1 可以成为组成部分么？如果不可以的话应该有些情况没有解如果可以有1 的
: 话贪心可以做吧
: 如果可以的话
: 我觉得可以
: while(n != 0) {
: m = Math.sqrt(n);
: result.add(m);
: n = n - m * m;
: }
: 假设输入是n = 14

s*m2015-08-01 07:08

12 楼

你真的是贝克汉姆啊！

【在 b******m 的大作中提到】

: 不是要求最小拆法吗？
: 要是48按你这算法就不是最小了。
: 楼上说的dp是啥？不懂呀。