动态规划计算累计概率问题

某游戏中有一个升级系统，每次尝试升级时，会有一定的概率成功或失败，成功后则等级+1，失败则等级不变。升级时会消耗一定的资源，升级成功的概率和资源的消耗量都仅与当前等级有关。具体规则如下：

当前等级	成功率	升级消耗
0 ~ 2	35%	10
3 ~ 6	20%	20
7	15%	30
8	10%	30
≥ 9	5%	50

一开始等级为0，玩家有且仅有20次升级尝试的机会，无论成功或失败都算作一次尝试。

问题：计算玩家用完20次升级尝试后，总消耗的资源的概率分布。

---

为了计算总消耗的分布，我们采用动态规划方法。

我们首先可以用数学方法可以得到以下两个简单的推论：

• 因为9级之后的消耗是固定的50，题目只是求解消耗，因此我们可以干脆认为9级必定失败，就不需要后续等级的状态了
• 20次最多消耗720（对应全部成功的情况），大于720的状态是不会达到的，并且消耗一定是10的倍数

定义状态 $dp[n][\ell][s]$ 表示经过 $n$ 次升级后，等级为 $\ell$，总消耗为 $s$ 的概率。其中：

• $n = 0,1,\dots,20$（升级次数）
• $\ell = 0,1,\dots,9$（等级）
• $s$ 为总消耗，是 10 的倍数，范围从 0 到 720

初始状态：$dp[0][0][0] = 1$。

状态转移：对于每个状态 $dp[n][\ell][s]$，根据当前等级 $\ell$ 查表得到消耗 $c(\ell)$ 和升级成功概率 $p(\ell)$。

• 如果 $\ell < 9$
  • 以概率 $p(\ell)$ 升级成功，转移到 $dp[n+1][\ell+1][s + c(\ell)]$。
  • 以概率 $1 - p(\ell)$ 升级失败，转移到 $dp[n+1][\ell][s + c(\ell)]$。
• 当 $\ell >= 9$ 时，消耗固定为 $c(9) = 50$。

最终，总消耗为 $s$ 的概率为 $\displaystyle\sum_{\ell=0}^{9} dp[20][\ell][s]$。

代码实现如下：

# 概率和消耗表
prob_main = [0.35]*3 + [0.2]*4 + [0.15, 0.1, 0.0]
cost = [10]*3 + [20]*4 + [30, 30, 50]

# 动态规划
dp = [[[0]*73 for _ in range(10)] for _ in range(21)]  # s/10 作为索引，最大72
dp[0][0][0] = 1.0

for n in range(20):
    for l in range(10):
        p = prob_main[l]
        c = cost[l] // 10  # 除以10作为索引步长
        for s_idx in range(73):
            prob = dp[n][l][s_idx]
            if prob == 0:
                continue
            # 升级失败
            dp[n+1][l][s_idx+c] += prob * (1-p)
            # 升级成功
            if l < 10:
                dp[n+1][l+1][s_idx+c] += prob * p

# 收集结果
dist = {}
for s_idx in range(73):
    total_prob = sum(dp[20][l][s_idx] for l in range(10))
    if total_prob > 0:
        dist[s_idx*10] = total_prob

# 按消耗排序输出
for s in sorted(dist.keys()):
    print(f"{s}: {dist[s]:.6f}")

最终可以得到总消耗的概率分布，如下图所示：