求解改良版划分问题：20次1-10随机变量抽样和的概率计算

方案1：动态规划（最适合当前场景，Python实现极简单） #

这是当前场景下性价比最高的方案，时间复杂度仅为O(n * max_sum * k)，其中n是抽取样本数（20），max_sum是最大和值（200），k是单变量取值个数（10），总运算量不到5万次，毫秒级即可出结果。

核心思路 #

定义dp[i][s]为抽取i个样本时，和为s的概率：

• 初始状态：dp[0][0] = 1.0（抽0个样本和为0的概率为1）
• 状态转移：对第i次抽取，每个可能的和值s，叠加单变量所有可能取值k的概率贡献：dp[i][s + k] += dp[i-1][s] * P[k-1]，其中P[k-1]是取值为k的概率
• 空间优化：因为第i次的结果仅依赖第i-1次的状态，可只用一维数组滚动更新，内存占用不到1KB

Python 示例代码 #

# 示例概率分布：X取1-10为均匀分布，可替换为你的实际P1-P10
P = [0.1] * 10
sample_cnt = 20
max_sum = sample_cnt * 10

# 初始化DP数组：dp[s]表示当前累计和为s的概率
dp = [0.0] * (max_sum + 1)
dp[0] = 1.0

for _ in range(sample_cnt):
    next_dp = [0.0] * (max_sum + 1)
    for s in range(len(dp)):
        if dp[s] == 0:
            continue
        # 遍历单变量所有可能取值
        for k in range(1, 11):
            if s + k > max_sum:
                continue
            next_dp[s + k] += dp[s] * P[k - 1]
    dp = next_dp

# 输出结果：dp[s]就是和为s的精确概率（浮点精度）
# 如需更高精度，可替换为fractions.Fraction或decimal.Decimal类型计算
for s in range(10, 201):
    print(f"和为{s}的概率：{dp[s]}")

方案2：生成函数卷积（适合更大规模的同类型问题） #

如果后续你需要处理样本数更大、单变量取值更多的场景，可以用生成函数结合快速卷积的方案：

• 单变量X的生成函数为 G(x) = P1*x + P2*x² + ... + P10*x¹⁰，其系数数组为[0, P1, P2, ..., P10]
• 20个独立X和的生成函数为G(x)^20，展开后x^s项的系数就是和为s的概率
• 实现时可通过快速幂+FFT卷积的方式计算，规模越大效率优势越明显，当前小场景下用DP更简单。

方案优势说明 #

两种方案都完全不需要枚举任何划分、组合，从根源上避免了你之前遇到的样本空间过大的问题，计算得到的是精确结果（仅受数值精度影响，可通过调整计算数值类型消除精度误差）。

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