计算n的互异部分整数分拆数 Python代码超时优化

互异部分整数分拆指和为n的严格递减正整数列表，每个数最多出现一次。例如n=5时共有3种符合要求的分拆：[5]、[4,1]、[3,2]。要求实现函数，返回1 <= n <= 600范围内整数对应的互异部分分拆总数。原有基于组合枚举的代码运行效率过低，会触发12000ms执行超时，优化方案如下。

• 采用itertools.combinations暴力枚举所有可能的数字组合，时间复杂度为指数级，n超过20时运行速度就会明显下降，n=600时完全无法在时限内跑完
• 对每个枚举出来的组合重复执行求和、判断0是否存在的操作，存在大量冗余计算

互异分拆计数是典型的01背包场景：

• 把分拆的和n看作背包总容量，1~n的每个正整数看作只能选1次的物品，选入物品的和等于背包容量时就对应一种合法分拆
• 提前预计算1~600所有n的分拆数，查询时直接返回结果即可，整体时间复杂度为O(n²)，n=600时仅需36万次运算，性能完全满足要求。

# 预计算所有1~600的分拆结果，全局只算一次
MAX_N = 600
dp = [0] * (MAX_N + 1)
dp[0] = 1  # 边界：和为0的空分拆共1种
for num in range(1, MAX_N + 1):
    # 01背包倒序遍历容量，避免同一个数字被重复选取
    for cap in range(MAX_N, num - 1, -1):
        dp[cap] += dp[cap - num]

def count_distinct_partitions(n):
    return dp[n]

• n=1时返回1，对应分拆[1]
• n=5时返回3，和示例结果完全匹配
• n=600的结果可以在毫秒级计算完成，不会触发超时

补充：根据欧拉分拆定理，互异部分分拆数和所有部分均为奇数的分拆数完全相等，基于该结论也可以写出性能相当的等价实现。

内容的提问来源于stack exchange，提问作者romulus cesar