计算分拆数p(n)是否有比欧拉五角数定理更优的算法？

更低复杂度的优化方案 #

首先澄清一个常见的复杂度认知偏差：基于欧拉五角数定理的原生动态规划解法，时间复杂度实际为O(n√n)，你提到的O(n²)是未引入五角数优化的普通完全背包型分拆计数算法的复杂度，O(n²log n)一般是带额外限制（比如每个拆分项有使用次数上限）的分拆问题的复杂度。
目前已经有成熟的优化方案可以把复杂度降到远低于O(n²)的水平：

• 基于生成函数+快速傅里叶变换（FFT）的方案：分拆数的生成函数为无穷乘积形式，通过多项式求逆 + NTT（数论变换，FFT的整数兼容版本）实现，时间复杂度可以降到O(n log²n)，是目前工业界计算大n分拆数的主流方案
• 近年还有进一步优化到*O(n log n)*的相关理论成果，已经在部分数学计算库中落地

最优性证明与复杂度类说明 #

目前不存在任何证明表明O(n²)或者O(n√n)是该问题的理论下界，同时计算整数分拆数也完全不属于NP难问题：

• NP难是针对判定类问题的复杂度分类，分拆数计算属于计数问题，目前已经有明确的多项式时间算法（上述FFT类方案就是多项式时间复杂度），不存在"降低到O(n²)以下是NP难"的说法
• 该问题的理论下界目前还没有明确结论，学界还在探索更优的实现方案

时空权衡方案 #

在时空复杂度均不超过O(n³)的限制下，完全可以实现两者的互换调整：

• 降空间、提时间：如果运行环境空间资源紧张，可以放弃预存全部分拆数前缀的DP数组，改用递归+滚动变量的方式实现五角数递推，空间最低可以压缩到O(√n)（仅需存储所有小于n的五角数数值），对应的时间复杂度会上升到O(n²)，仍远低于O(n³)的限制
• 降时间、提空间：如果需要高频查询不同n的分拆数，可以提前预计算p(1)到p(max_n)的所有结果存入数组，额外付出O(n)的空间开销，后续单次查询的时间复杂度直接降到O(1)；如果需要支持分拆方案的具体回溯，也可以预存分拆路径表，空间上升到O(n²)，仍符合限制要求

内容的提问来源于stack exchange，提问作者Subhankar Ghosal