您是project euler上那位6分钟求解出problem 618的大神baihaker吗？

[shousunny]

请教一下求解算法～～～

[baihacker]

用dp[i][j]表示用了第i个素数且和为j的时候的答案。需要注意的是：一个素数可以为和贡献k*p，同时对积贡献p^k，如何处理这个情况。

[shousunny]

dp[1][8]＝2x2x2x2+2x3x3＝34
dp[2][8]＝2x3x3+3x5＝33
是这样吗？

[baihacker]

dp[1][8] = 2x2x2x2 = 16
dp[2][8] = 2x2x2x2 + 2x3x3 = 34

update: 用dp[i][j]表示用了第1到第i个素数且和为j的时候的答案

[shousunny]

然后把答案存储起来，下次分解时直接进行查询是吗？

[baihacker]

dp[N][F[2]] + dp[N][F[3]] + ... + dp[N][F[24]] 就是结果了。
第N个素数是不超过F[24]的最大的素数。

[shousunny]

嗯，难点就在dp[N][F(24)]，这种F[24]很大时的求解，指数增长的计算量，

[baihacker]

F(24) = 46368，不超过F[2]的素数有4794个，所以一共有4794x46368=222288192约2亿个状态。
最后的dp：2亿多个状态，状态转移耗费O(1)，空间只要O(F[24])。
没有指数级增长的计算量。

[shousunny]

dp[3][15]＝dp[2][15]+5xdp[3][15-5]，
是通过这种方式，由小到大递推求解，下标数字较大的dp[i][j]吧？

[baihacker]

差不多是这样，过了？

[shousunny]

Python里边建不了4794x46386这么大的矩阵，我还得摸索一下怎么实现您教授的方法。

[baihacker]

你可以搜索一下滚动数组。甚至对于这个题，滚动数组都不用。

[shousunny]

过了~
什么时候才能像你这么优秀！

[shousunny]

最后一个问题，嘿嘿，提交答案后，euler如何知道您只花了6分钟解出了答案?如何上最快解题榜?

[baihacker]

解题时间从题目发布开始计时。想上榜可以在题目发布时开始做，至于耗时就因素众多了。

[shousunny]

我的代码光运算就花了3分钟……
您这是几分钟内就编出了正确可运行的代码……
望尘莫及，佩服！佩服