You need to enable JavaScript to run this app. 使用递归方法时如何解决Python组合计算出现的MemoryError问题
优惠活动
大模型
产品
解决方案
定价
更多

使用递归方法时如何解决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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.20 23:54:06