logo
Redian新闻
>未名空间
>PhotoGear - 摄影器材
>
这是什么价格？
avatar
这是什么价格？# PhotoGear - 摄影器材
u*l
1 楼
2个烙印，上来就是这么一道：
题目描述起来很简单，就是给出一个数，找出所有Unique的组合。
比如： 2 ：　１＋１
３：　　１＋２，　１＋１＋１
４：　　１＋３，　１＋２，　１＋１＋１＋１，　２＋２
被追问Complexity。
现在也没有想明白，牛人来答答吧。
问烙印是不是N3，烙印不置可否。
avatar
t*t
3 楼
O(n)吧。
avatar
a*9
4 楼
骗子
avatar
b*o
5 楼
Partition number:
http://en.wikipedia.org/wiki/Partition_(number_theory)
根据wiki上的递推公式，O(n^2)还是能做到的，就是不知道是不是最优了。

【在 u*l 的大作中提到】
: 2个烙印，上来就是这么一道：
: 题目描述起来很简单，就是给出一个数，找出所有Unique的组合。
: 比如： 2 ：　１＋１
: ３：　　１＋２，　１＋１＋１
: ４：　　１＋３，　１＋２，　１＋１＋１＋１，　２＋２
: 被追问Complexity。
: 现在也没有想明白，牛人来答答吧。
: 问烙印是不是N3，烙印不置可否。
avatar
u*l
7 楼
我擦，今天知道了，烙印给我很差的评价，说答案不是最优。
30分钟内让我搞定这个，真够黑。

【在 b*****o 的大作中提到】
: Partition number:
: http://en.wikipedia.org/wiki/Partition_(number_theory)
: 根据wiki上的递推公式，O(n^2)还是能做到的，就是不知道是不是最优了。
avatar
a*l
8 楼
100%好评?

【在 a*******9 的大作中提到】
: 骗子
avatar
f*s
9 楼
我只能想到一个O(n^2)的
avatar
h*e
10 楼
当然是骗子啦~~
版上说过好多次了吧？
avatar
l*i
11 楼
大牛给说说N^2思路。

【在 f******s 的大作中提到】
: 我只能想到一个O(n^2)的
avatar
h*e
12 楼
盗号

【在 a********l 的大作中提到】
: 100%好评?
avatar
s*s
13 楼
如果只是数所有unique的组合的数目，可以O(n^2).
但是如果找到所有的unique的组合，我怎么都想不出来如何O(n^2)做到，请大牛指教。

【在 f******s 的大作中提到】
: 我只能想到一个O(n^2)的
avatar
a*l
14 楼
哦，黑客们搞这个干什么呢？

【在 h*******e 的大作中提到】
: 盗号
avatar
w*8
15 楼
2^(n-1)
avatar
t*8
16 楼
赚钱

【在 a********l 的大作中提到】
: 哦，黑客们搞这个干什么呢？
avatar
l*i
17 楼
agree to this. looks like a pseudo polynomial?

【在 w********8 的大作中提到】
: 2^(n-1)
avatar
a*l
18 楼
可钱是发到这个账户真正的拥有者的账上啊？

【在 t*******8 的大作中提到】
: 赚钱
avatar
l*i
19 楼
我能想到的，就是combination sum的解法。
avatar
a*9
20 楼
所以才让你联系他。然后直接打到他账户去了。

【在 a********l 的大作中提到】
: 可钱是发到这个账户真正的拥有者的账上啊？
avatar
z*e
21 楼
先取一个n高的高度
然后把n顶端的那个1往右边走
比如5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
总共有n行，每一行都不超过n个数，你要做的就是筛选掉不合格的组合
而所谓不合格的就是当前高度大于左边的高度的情况，比如
2+2+1之后的
2+1+2，最后一个2大于左边的1，干掉
如果合格的组合，就放到result list里面去
所以最后复杂度是n^2
递推公式别管了，用欧拉命名的公式和定理，可想而知了
avatar
h*e
22 楼
叫你联系的那个email可不是账户的真正拥有者阿
email里可不会叫你把钱送给真正拥有者。。。。

【在 a********l 的大作中提到】
: 可钱是发到这个账户真正的拥有者的账上啊？
avatar
c*z
23 楼
DP不是O（n）么
另，记下这题了，以后考烙印给lz报仇 ：）
avatar
a*l
24 楼
我果然够笨的，多谢各位点通我。
avatar
c*p
25 楼
应该能利用上以前的结果。
avatar
y*0
26 楼
刚才版上有个兼职广告, 也是骗子? 俺还去信问了问, 有没事?
avatar
r*n
28 楼
明显不是n行啊？ 你这个例子已经是6行了啊。
如果是6
5 1
4 2
4 1 1
3 2 1
3 1 1 1
2 2 1 1
2 1 1 1 1
1 1 1 1 1 1
已经8行了
数字越大，越来越多的行会已相同的数字开头，所以行数会远远大于n。wiki上面p(100
) =190,569,292，如果真的有O(n^2)算法存在，p(100)最多是10000，因为你最多只能
做10000次比较。
按照wiki上面的recursion formula
p(1, n) = 1 + sum_{k=1}^{n/2}p(k, n-k)
这个复杂度是O(2^{n/2})
PS：这个题要不是见过，基本没有可能现场推出来wiki的公式。下次大家面烙印的时候
不用手软了，直接上来第一题就让他证明yitang的7千万。

【在 z****e 的大作中提到】
: 先取一个n高的高度
: 然后把n顶端的那个1往右边走
: 比如5
: 4+1
: 3+2
: 3+1+1
: 2+2+1
: 2+1+1+1
: 1+1+1+1+1
: 总共有n行，每一行都不超过n个数，你要做的就是筛选掉不合格的组合
avatar
r*n
29 楼
上面有人说用DP，或者DP + subset with duplicates，我最先也是这么想的，但是中
间会有重复的。
avatar
z*e
30 楼
用hashset干掉duplicates

【在 r*********n 的大作中提到】
: 上面有人说用DP，或者DP + subset with duplicates，我最先也是这么想的，但是中
: 间会有重复的。
avatar
z*e
31 楼
dp应该是n^3的复杂度
每一次都从之前的答案中挨个拿出来
对每一个的每一位挨个加1看结果，这一步复杂度是n^2
然后放入set中，然后再在set里面去掉重复的数据，复杂度是n
n所以最后复杂度是n^3
n^3强过递归的2^n的复杂度
也就是说楼主说的是对的咯？

【在 r*********n 的大作中提到】
: 上面有人说用DP，或者DP + subset with duplicates，我最先也是这么想的，但是中
: 间会有重复的。
avatar
p*3
32 楼
O(n^2)
DP不会有重复，用recursion和二位DP矩阵还原解决方案
avatar
r*n
33 楼
貌似是这样的，用wiki上面的公式和2维dp记录p(k, n-k)

【在 p*****3 的大作中提到】
: O(n^2)
: DP不会有重复，用recursion和二位DP矩阵还原解决方案
avatar
x*s
34 楼
可以看成一个换零钱的问题，给一个面额是n的钞票，和一组可以重复使用的零钞{1,2,
3,...,n-1}，问一共有多少种换法。一个backtracking就解决了
avatar
p*3
35 楼
const int N = 100;
void printWays(int dp[N][N], int i, int j, vector& vec)
{
if (i < 0 || j < 0 || dp[i][j] <= 0)
return;
if (j == 0)
{
for (vector::iterator it = vec.begin(); it != vec.end(); it++)
cout<cout<return;
}
vec.push_back(i);
printWays(dp, i, j-i, vec);
vec.pop_back();
printWays(dp, i-1, j, vec);
}
int getUniqueWays(int n)
{
if (n <= 0)
return 0;
int dp[N][N] = { 0 };
for (int i = 0; i <= n; i++)
{
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
dp[i][j] = dp[i-1][j];
if (j >= i)
dp[i][j] += dp[i][j-i];
}
}
vector vec;
printWays(dp, n, n, vec);
return dp[n][n];
}
n^2 无重复
avatar
i*7
36 楼
我觉得这咋看都是一个递归吧。
avatar
f*s
37 楼
不好意思,写错了,是O(2^n)
run...

。

【在 s*******s 的大作中提到】
: 如果只是数所有unique的组合的数目，可以O(n^2).
: 但是如果找到所有的unique的组合，我怎么都想不出来如何O(n^2)做到，请大牛指教。
avatar
k*o
38 楼
很有意思，学习了。
avatar
x*0
39 楼
mark
相关阅读
cayi 是翻唱高手？为啥x100在800就不再跌了?【WTB】5D3 Body Only @ 3000看了Galcat 的flickr4500。。。背在胸前的dslr包奔2张混血[合集] 谣传方励之逝世XXB IS多少算不错的dealD300只要500了询问下，B&H上卖的import的镜头靠谱么？昨天晚上去看了American Reunionx大师上毛豆集体照了万佛，1700的D700算deal吗？82mm 口径的lens是今年的流行趋势俺也去晃动物园了 (转载)今天碰到的这人是大师吗？Canon 28-135 IS 能出多少钱？为什么D800的颜色很干涩，层次感不强？5DIII漏光了？CR
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。