概率 DP

例题一：带陷阱的棋盘期望步数

题目描述

有一个长度为 $n$ 的棋盘，起点在1号格，每次可以掷骰子前进1~6步。如果踩到棋盘上的某些“陷阱格”，就会直接回到起点。问：从起点出发到终点的期望步数。

---

1. 状态定义

• $f[i]$：从第 $i$ 格到终点的期望步数

---

2. 状态转移

每次可以前进1~6步，每种情况概率 $\frac{1}{6}$。 如果 $i+k$ 是陷阱，就会直接回到1号格，否则就前进到 $i+k$。

所以：

$f[i] = 1 + \frac{1}{6} \sum_{k=1}^{6} \begin{cases} f[1] & \text{如果 } i+k \text{ 是陷阱} \\ f[i+k] & \text{否则} \end{cases}$

边界条件：$f[n] = 0$（到终点不需要再走）

---

3. 思路要点

• 需要特殊判断“陷阱”，状态转移会“跳回头”，增加难度。

• 可以用类似前面的方法自底向上递推。

---

例题二：青蛙跳格子的概率（带障碍）

题目描述

有一条 $n$ 格的路，青蛙在1号格，每次等概率跳1~2步。有的格子上有障碍，跳到障碍会死掉（结束）。问：青蛙能活着跳到终点的概率是多少？

---

1. 状态定义

• $f[i]$：青蛙从第 $i$ 格活着跳到终点的概率

---

2. 状态转移

• 如果 $i$ 是障碍，$f[i] = 0$

• 如果 $i \geq n$，$f[i] = 1$（终点）

• 否则：$f[i] = 0.5 \times f[i+1] + 0.5 \times f[i+2]$

---

3. 思路要点

• 障碍格直接判为0。

• 其余状态正常转移。

• 多一步判断条件而已。

---

例题三：有保底的抽卡期望

题目描述

某游戏抽卡，单抽出 SSR 概率为 $p$，连续抽 $k$ 次没出，下一次必定出（即“保底”）。问：期望抽到SSR所需的抽卡次数是多少？

---

1. 状态定义

• $f[i]$：已经连续失败了 $i$ 次，接下来抽到SSR的期望次数。

---

2. 状态转移

• 当 $i = k$：保底了，必出，$f[k] = 1$

• $i < k$ 时：

  • 本轮抽中 SSR（概率 $p$）：1次结束

  • 没抽中（概率 $1-p$）：又多抽一次，失败数 +1，变成 $f[i+1]$

$f[i] = p \cdot 1 + (1-p) \cdot (1 + f[i+1])$

---

3. 求解方式

可以递推，也可以递归+记忆化。实际写代码时从 $k$ 往前递推到 0，就是期望所需次数。

---

例题四：两人博弈胜利概率

题目描述

两人轮流投硬币，谁先正面朝上谁赢。每次投正面概率 $p$。问：第一个人获胜的概率是多少？

---

1. 状态定义

• $f$：当前轮到你时，你获胜的概率

---

2. 状态转移

• 你这轮投到正面，直接赢，概率 $p$。

• 没投到，轮到对手，对手也有同样的策略，所以概率是 $1 - f$。

$f = p \cdot 1 + (1-p) \cdot (1 - f)$

解这个方程即可。

---

例题五：随机走格子的期望

题目描述

有一个N*N的棋盘，每一步等概率向上下左右走，不能走出边界。问：从左上角走到右下角的期望步数是多少？

---

1. 状态定义

• $f[x][y]$：从点 $(x,y)$ 走到终点的期望步数

---

2. 状态转移

对于每个方向都要考虑边界条件。

$f[x][y] = 1 + \frac{1}{d} \sum f[\text{next}(x, y)]$

其中 $d$ 是有效方向数。

---

总结

常见概率DP考点：

• 期望步数/次数型（带障碍、带保底等）

• 到达终点概率型（路径有生死、博弈等）

• 棋盘型/二维DP

• 动态状态转移、嵌套概率、循环依赖