使用递归方法时如何解决Python组合计算出现的MemoryError问题
问题原因分析
你当前的实现触发MemoryError的核心原因是暴力生成并存储了所有长度≥2的整数组合,当n=50时,1到49的所有符合长度要求的组合总量达到2^49量级,完全超出普通设备的内存承载上限,同时该实现也没有用到递归,不符合作业要求。
递归方案实现思路
这个问题本质是统计「将n拆分为至少2个互不相同正整数之和的拆分方案数」,为了避免重复计数(比如1+4和4+1视为同一种方案),递归逻辑我们做如下约束:每次选择的数必须严格大于上一次选择的数。
我们可以定义带记忆化的递归函数dp(remaining, start),两个参数的含义分别为:
remaining:当前还需要凑出的和start:下一个可选的最小正整数
边界条件
- 若
remaining == 0:说明找到一个合法拆分方案,返回1 - 若
remaining < start:后续可选的数都大于等于start,不可能凑出剩余值,返回0
递归逻辑
每一步我们都有两种选择:
- 选择
start作为拆分的下一个数:剩余待凑和变为remaining - start,下一个可选的最小数变为start + 1,对应方案数为dp(remaining - start, start + 1) - 不选择
start:剩余待凑和不变,下一个可选的最小数变为start + 1,对应方案数为dp(remaining, start + 1)
最终staircase(n)的结果为dp(n, 1) - 1,减去1是为了排除「仅选择n自己」的方案(作业要求组合至少包含2个正整数)。
完整代码实现
from functools import lru_cache def staircase(n): @lru_cache(maxsize=None) def dp(remaining, start): if remaining == 0: return 1 if remaining < start: return 0 # 选start + 不选start 的方案数之和 return dp(remaining - start, start + 1) + dp(remaining, start + 1) # 减去只有n一个元素的方案 return dp(n, 1) - 1 print(staircase(50))
代码说明
- 用
lru_cache做记忆化缓存,避免重复计算相同参数的递归结果,大幅提升运行效率,n=50的场景下运行无压力,不会出现内存溢出问题 - 全程没有生成和存储所有组合,仅通过递归计数,内存占用极低
- 完全符合递归实现的作业要求
内容的提问来源于stack exchange,提问作者Ejin
相关产品推荐
相关产品推荐

