[!info] related notes 动态规划

概率 DP

一句话定义

概率 DP 是动态规划的一个子类型，其中状态转移基于概率加权而非最优值选取，用于求解涉及随机事件的概率或期望值问题。

核心机制 / 工作原理

核心思想

普通 DP 的转移是 max/min/sum，概率 DP 的转移是 加权平均：

• 概率型：状态值 = 所有来源状态概率 × 转移概率 之和
• 期望型：状态值 = 当前代价 + 所有后继状态期望的加权平均

关键区别：概率 DP 不做”选择”，而是按随机事件的概率分布求和。

常见模型

模型	状态含义	转移方向
成功概率	dp[i] = 从状态 i 出发到达目标的概率	正向或反向
期望步数	f[i] = 从状态 i 出发到结束的期望步数	反向（从终态推）
博弈论概率	dp[i] = 当前玩家在状态 i 的获胜概率	反向

解题模板

1. 定义状态：明确 dp[i] 代表什么概率或期望
2. 确定转移：列出所有可能的随机事件及其概率
3. 写方程：
   - 概率型：dp[i] = sum(dp[j] * p(i→j))  对所有 j
   - 期望型：f[i] = cost(i) + sum(f[j] * p(i→j))  对所有 j
4. 确定边界：终态的概率或期望值
5. 确定计算顺序：拓扑序或高斯消元

最小例子

问题：一个骰子有 6 面，从 0 出发，每次掷骰子前进对应步数，求到达位置 N 的期望掷骰次数。

# f[i] = 从位置 i 出发到达 N 的期望掷骰次数
# f[N] = 0  (已到达)
# f[i] = 1 + (f[i+1] + f[i+2] + ... + f[i+6]) / 6  (for i < N)

def expected_rolls(N):
    f = [0.0] * (N + 1)
    for i in range(N - 1, -1, -1):
        f[i] = 1.0
        for j in range(1, 7):
            if i + j <= N:
                f[i] += f[i + j] / 6.0
    return f[0]

转移方程中的 1 是”当前这一步”的代价，f[i+j]/6 是每个后继状态期望的加权平均。

与其他 DP 类型的区别

维度	普通 DP	概率 DP
转移方式	max / min / sum	概率加权求和
有无选择	有（最优子结构）	无（按概率分布）
状态值含义	最优值	概率或期望
计算顺序	通常拓扑序	拓扑序或高斯消元

边界与常见误解

• 概率和期望不要混用：概率是 [0,1] 的值，期望可以是任意正数。两者转移方程不同，不要混在一个状态里
• 漏掉总概率为 1 的约束：所有转移概率之和必须为 1，否则结果会偏
• 期望转移里忘记当前步代价：f[i] = 1 + sum(...) 中的 1 不能漏，它是”本次操作”的代价
• 精度问题：浮点运算累积误差，竞赛中通常 double 足够，但要注意避免极小概率相乘导致下溢
• 环形依赖：如果状态转移存在环（如博弈论），需要高斯消元而不是简单递推
• 不等于贪心：概率 DP 不能贪心选”最可能的路径”，必须按概率加权所有可能

学习建议

• 先熟悉普通 DP 的状态定义和转移
• 再做概率 / 期望 DP，因为本质还是”定义状态 + 写转移”
• 从一维线性模型开始（如掷骰子、随机游走），再做二维和博弈论模型

Related notes

• 动态规划