Python中如何高效计算N个离散随机变量之和的概率

原递归解法存在大量重复子问题计算：不同的路径选择最终会落到相同的start索引和相同的剩余L值，导致同一段逻辑被反复执行，当N接近20时，4^20的指数级运算量完全无法在合理时间内跑完。下面提供两种可直接落地的优化方案，都能在毫秒级完成N=20的计算：

方案1：记忆化搜索（改动最小） #

仅需给原递归函数加缓存即可，不用修改核心计算逻辑，缓存会自动把重复子问题的结果复用：

from functools import lru_cache

N = 15
times_distribution = [[[v, 1 / 4] for v in (30, 60, 90, 120)] for n in range(N)]
times_distribution[0] = [[0, 1]]
path = tuple(range(N)) + (0,) # 转成元组作为全局固定值，避免作为缓存入参
L = 1000

@lru_cache(maxsize=None)
def calculate_from(start, remain_L):
    if start == len(path) - 1:
        return 1 if remain_L < 0 else 0
    total = 0
    for value, p in times_distribution[path[start]]:
        total += p * calculate_from(start + 1, remain_L - value)
    return total

prob = 1 - calculate_from(0, L)

方案2：迭代动态规划（效率最高） #

基于离散分布的卷积原理，逐次迭代计算前k个变量和的概率分布，复杂度仅为O(N * 最大可能和的数量)，你的场景下总运算量不到10万次，几乎瞬间出结果：

N = 15
times_distribution = [[[v, 1 / 4] for v in (30, 60, 90, 120)] for n in range(N)]
times_distribution[0] = [[0, 1]]
path = list(range(N)) + [0]
L = 1000

# 初始化分布：初始和为0，概率1
dist = {0: 1.0}
for idx in path[:-1]: # 遍历所有需要计算的变量节点
    new_dist = {}
    for cur_sum, cur_p in dist.items():
        for value, p in times_distribution[idx]:
            new_sum = cur_sum + value
            new_dist[new_sum] = new_dist.get(new_sum, 0) + cur_p * p
    dist = new_dist

# 直接统计所有和大于L的概率总和
prob = sum(p for s, p in dist.items() if s > L)

可选优化 #

由于你所有变量的取值都是30的倍数，可以统一把所有值除以30（30→1、60→2、L→L//30），缩小数值范围后字典操作的速度会更快。

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