f*********5
发帖数: 66 | 1 我的想法是贪心，每次找出最大的再减去，不过总感觉不对，请问正确的做法是？ |
b******m
发帖数: 382 | 2 这是算法题吗？
一个一个试吧。
先把所有比这个数小的平方数找出来，看看能不能写成2个的和。
不行，就看看能不能写成3个的。。。
手算的话应该没什么好办法。 |
r******y
发帖数: 21 | 3 这个有两种解法：
第一种是DP，先在O(sqrt(n))时间找出所有平方数因子，然后用coin change找出最少
组合。
第二种是深搜，也是先在O(sqrt(n))时间找出所有平方数因子，然后就暴力深搜，但是
深搜的最大深度是3，如果都搜不到就返回4. (拉格朗日平方数和定理) |
f*********5
发帖数: 66 | 4
想法非常好！感谢
【在 r******y 的大作中提到】
: 这个有两种解法：
: 第一种是DP，先在O(sqrt(n))时间找出所有平方数因子，然后用coin change找出最少
: 组合。
: 第二种是深搜，也是先在O(sqrt(n))时间找出所有平方数因子，然后就暴力深搜，但是
: 深搜的最大深度是3，如果都搜不到就返回4. (拉格朗日平方数和定理)
|
T*****u
发帖数: 7103 | |
s*****m
发帖数: 8094 | 6
人要的是“最小拆法”，不是“4”
【在 r******y 的大作中提到】
: 这个有两种解法：
: 第一种是DP，先在O(sqrt(n))时间找出所有平方数因子，然后用coin change找出最少
: 组合。
: 第二种是深搜，也是先在O(sqrt(n))时间找出所有平方数因子，然后就暴力深搜，但是
: 深搜的最大深度是3，如果都搜不到就返回4. (拉格朗日平方数和定理)
|
s****a
发帖数: 794 | |
w******n
发帖数: 61 | |
j********2
发帖数: 414 | 9 请问 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******m
发帖数: 382 | 10 不是要求最小拆法吗？
要是48按你这算法就不是最小了。
楼上说的dp是啥？不懂呀。
【在 j********2 的大作中提到】
: 请问 1 可以成为组成部分么？ 如果不可以的话 应该有些情况没有解 如果可以有1 的
: 话贪心可以做吧
: 如果可以的话
: 我觉得 可以
: while(n != 0) {
: m = Math.sqrt(n);
: result.add(m);
: n = n - m * m;
: }
: 假设 输入是n = 14
|
s*****m
发帖数: 8094 | 11
你真的是贝克汉姆啊！
【在 b******m 的大作中提到】
: 不是要求最小拆法吗？
: 要是48按你这算法就不是最小了。
: 楼上说的dp是啥？不懂呀。
|
