概率与期望 DP
动态规划 ⭐⭐⭐ 进阶 💧 低频
💡 核心要点
概率 DP 正向累积概率，期望 DP 逆向递推代价，两者方向相反是最核心的区别。
识别信号
- 题目涉及随机事件、概率分布或期望值计算
- 关键词出现：概率、期望、随机、骰子、均匀分布、随机游走
- 求某个事件发生的概率（如"棋子最终留在棋盘上的概率"）
- 求从初始状态到达目标状态的期望步数、期望代价或期望轮数
- 状态之间的转移带有概率权重，而非确定性跳转
通用思考框架
概率 DP（正向推进）
表示到达状态 的概率，从初始状态出发，沿转移方向正向累积：
- 初始状态概率为 1，其余为 0
- 每一步将当前状态的概率按转移权重分配到后继状态
- 最终答案是目标状态的概率之和
期望 DP（逆向推进）
表示从状态 出发到达目标的期望步数/代价，从目标状态出发，逆向向起始状态推：
- 目标状态的期望代价为 0（已到达，无需额外代价）
- 每个状态的期望 = 所有可能转移的（后继期望 + 本步代价）的概率加权和
- 最终答案是初始状态的 值
方向对比总结
| 类型 | 方向 | 初始值 | 转移含义 |
|---|---|---|---|
| 概率 DP | 正向（起点 → 终点） | 起点概率 = 1 | 概率向后继状态扩散 |
| 期望 DP | 逆向（终点 → 起点） | 终点期望 = 0 | 期望从后继状态向前累积 |
浮点数注意事项
- 统一使用
double，避免用float（精度不足） - 题目若要求误差在 以内，
double通常足够 - 概率之和在每一步应等于 1，可用于调试验证
典型例题：骑士在棋盘上的概率 LeetCode 688
题目描述
在 的棋盘上，骑士从位置 出发，每次随机等概率选择 8 个马步方向之一移动，共移动 步。求骑士最终仍留在棋盘上的概率。
五步法分析
第一步：定义状态
= 骑士在第 步时位于格子 的概率。
第二步：状态转移
骑士从 出发，以均等概率 跳向每个合法方向 ：
这是正向概率 DP：从当前状态将概率分发给后继状态。
第三步：初始条件
骑士初始以概率 1 位于起点 。
第四步：计算顺序
按步数从 到 逐步推进，每步遍历所有格子，将概率扩散到下一步的合法位置。
第五步：提取答案
第 步时，所有仍在棋盘内的格子概率之和即为答案：
Java 完整代码
class Solution {
public double knightProbability(int n, int k, int row, int column) {
// 马的 8 个跳跃方向
int[][] dirs = {
{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
{ 2, -1}, { 2, 1}, { 1, -2}, { 1, 2}
};
// dp[i][j] 表示当前步骑士位于 (i, j) 的概率
double[][] dp = new double[n][n];
dp[row][column] = 1.0;
for (int step = 0; step < k; step++) {
double[][] next = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][j] == 0) continue; // 剪枝：概率为 0 无需扩散
for (int[] dir : dirs) {
int ni = i + dir[0];
int nj = j + dir[1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
// 正向概率转移：将概率的 1/8 分配给后继状态
next[ni][nj] += dp[i][j] / 8.0;
}
// 跳出棋盘的部分概率自然消失，无需处理
}
}
}
dp = next;
}
// 累加所有格子的概率，即为留在棋盘上的总概率
double result = 0.0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result += dp[i][j];
}
}
return result;
}
}复杂度分析：
- 时间复杂度：
- 空间复杂度：（滚动数组优化后只需两层）
延伸题目
| 题目 | 链接 | 类型 | 关键思路 |
|---|---|---|---|
| 新 21 点 | LC 837 | 概率 DP | 正向推进，用前缀和优化转移 |
| 分汤 | LC 808 | 概率 DP | 状态为剩余汤量，大数据时概率趋近 1 可剪枝 |
| 抛掷硬币 | LC 1230 | 概率 DP | = 前 枚硬币恰好 枚正面的概率 |
| 24 点游戏 | LC 679 | 期望 DP / 搜索 | 枚举运算顺序，判断能否凑出目标值 |
常见陷阱与调试
1. 概率 DP 和期望 DP 推进方向搞反
概率 DP 必须正向推进（起点 → 终点），因为当前状态的概率依赖于前驱状态已经确定的概率。期望 DP 必须逆向推进（终点 → 起点），因为当前状态的期望依赖于后继状态的期望。方向搞反会导致依赖的值尚未计算，结果错误。
2. 浮点精度问题
使用 float 在多步累加后误差会超出题目要求，统一使用 double。若题目允许整数分数表示，也可用分子分母分别维护，但通常 double 已足够。
3. 概率之和不为 1（状态遗漏）
正常情况下，所有可达状态的概率之和应等于初始概率 1.0。如果中途发现概率之和小于 1，说明有部分概率"泄漏"到了非法状态（如本题跳出棋盘），这是正常现象；若发现概率之和大于 1，则说明转移公式有误，存在重复计数。
4. 期望 DP 中忘记加每步代价
期望 DP 的转移公式是 ，其中 通常为 1（走这一步本身的代价）。漏掉 +1 是高频错误，会导致期望值偏小。
5. 环状依赖（期望 DP 有环）
若状态转移图存在环（如随机游走可能回到当前状态），朴素递推无法直接使用，需建立方程组用高斯消元求解，或用迭代法（值迭代）逼近不动点。