概率期望DP

以下是对概率期望DP的系统化整合，采用"理论框架→核心模型→实战技巧→避坑指南"的四层结构，结合两份资料精华优化而成：

一、理论框架（核心数学工具）

1. 概率与期望的本质

• 概率：事件发生的可能性，取值范围 $[0,1]$。例如掷骰子出现点数为 $1$ 的概率为 $1/6$。
• 期望（E）：随机变量的加权平均值，反映长期均值。公式为 $E(X)=\sum (x_i\cdot P(x_i))$，如掷骰子的点数期望为 $(1+2+3+4+5+6)/6=3.5$。

2. 期望的线性性质

期望的线性性（无论事件是否独立）：
$$E[aX+bY]=aE[X]+bE[Y]$$

推广：$E(\sum X_i)=\sum E(X_i)$，该性质常被用于拆分复杂期望为简单期望的和。

应用场景：组合期望计算（如骰子点数和期望）
证明思路：利用期望定义式展开求和
$$E[X]=\sum _{x}x\cdot P(X=x)$$

3. 状态转移方程

(1) 通用转移方程

• 概率 DP：$dp[i]=\sum (dp[j]\cdot p_{j\to i})$，其中 $p_{j\to i}$ 是从状态 $j$ 转移到 $i$ 的概率。
• 期望 DP：$E[i]=\sum (p_j\cdot (E[j]+c_{i\to j}))+c_i$，其中：
  • $E[i]$ 是状态 i 的期望，
  • $p_j$ 是转移概率，
  • $c_{i\to j}$ 是转移代价，
  • $c_i$ 是当前状态的固定代价。

• 特殊处理：
  • 边界条件（如$E[n]=0$）
  • 概率归一化（当$\sum p_j<1$时）

(2) 典型状态定义案例

• 骰子爬楼梯问题：设 $E[i]$ 为从第 $i$ 级到终点的期望步数，则：
  $E[i]=1+\frac{1}{6}(E[i+1]+E[i+2]+\cdots +E[i+6])(i<n),E[n]=0$
• 赌徒破产问题：设 (dp[i]) 为有 i 元时赢到 N 元的概率，则：
  $dp[i]=p\cdot dp[i+1]+(1-p)\cdot dp[i-1],dp[0]=0,dp[N]=1$

4. 概率 DP 与期望 DP 的区别

• 概率 DP：已知初始状态，顺推目标状态的概率（如从起点到终点的成功概率）。
• 期望 DP：倒推求解，设 $f[i]$ 为从状态 $i$ 到目标的期望，初始时目标状态的期望为 0（如到达终点的期望步数）。

5. 数学工具箱

• 高斯消元法：处理环形状态依赖（如赌徒破产问题）
• 生成函数：解决复杂递推关系
• 蒙特卡洛验证：期望值近似验证（误差控制在$1e-6$内）

二、核心模型（经典问题类型）

1. 线性无环模型

典型题：骰子爬楼梯（Codeforces 1237E）

从 $0$ 级出发，每次掷 $1-6$ 点骰子，求到达 $n$ 级的期望步数。

//迭代优化版:时间复杂度O(n)
double dp[MAXN];
for(int i = n-1; i >= 0; --i){int steps = min(6, n-i);double sum = 0;for(int j = 1; j <= steps; ++j)sum += dp[i+j];dp[i] = 1+sum/6.0;
}

关键优化：

• 前向遍历会导致数据污染
• 逆向遍历保证依赖关系正确

2. 树形期望模型

典型题：树上的随机游走（AtCoder DP E）

在有根树中，每个节点等概率走向父节点或子节点，求从 $u$ 到根的期望步数。

状态转移：设 $E[u]$ 为从 $u$ 到根的期望，$u$ 的子节点数为 $k$，则：
$E[u]=1+\frac{1}{k+1}E[parent]+\frac{1}{k+1}\sum E[child]$

// 后序遍历实现
inline void dfs(int u, int fa){if(u是叶子){E[u] = 0;return;}double sum = 0;for(int v: ch[u]){if(v != fa){dfs(v, u);sum += E[v];}}E[u] = 1+(sum+E[fa])/(cnt+1);
}

关键特性：

• 子节点期望值优先计算
• 父节点期望值作为中间变量

3. 环形依赖模型

典型题：赌徒破产问题（数学解法）

当状态转移方程形成环（如 $E[i]$ 依赖 $E[i-1]$ 和 $E[i+1]$），需建立线性方程组求解。
解法：将递推式转化为 $a_{i}E[i-1]+b_{i}E[i]+c_{i}E[i+1]=d_i$，通过高斯消元解方程组。

// 当p ≠ q时通解公式
inline double solve(int i, int N, double p){double q = 1-p;return (pow(q/p, i)-1) / (pow(q/p, N)-1);
}

数学推导：

1. 建立差分方程：$E[i]=pE[i+1]+qE[i-1]+1$
2. 特解+通解法求解
3. 边界条件代入求系数

三、实战技巧（代码优化策略）与应用

1. 空间优化

• 滚动数组：

double prev, curr;
for(int i=n-1; i>=0; --i){curr = 1;for(int j=1; j<=6; ++j)curr += prev;curr /= 6.0;prev = curr;
}

• 记忆化递归：适用于小状态空间，通过缓存避免重复计算。
• 迭代 DP：逆向递推（如从 $n$ 到 $0$），时间复杂度更低。

• 适用场景：状态只依赖相邻有限步

2. 精度控制

• 误差消除技巧：

// 双精度校验
double a = 1.0/3.0 + 1.0/3.0 + 1.0/3.0;
assert(fabs(a - 1.0) < 1e-9);

• 高精度方案：

#include <boost/multiprecision/cpp_dec_float.hpp>
using dec = cpp_dec_float_50;

• 状态压缩：用滚动数组将 $dp[i][j]$ 压缩为 $dp[j]$，节省空间。

3. 概率归一化

// 动态归一化处理
double total = 0.0;
for(auto [to, p] : transitions)total += p;
for(auto &[to, p] : transitions)p /= total;

4. 高斯消元模板（环形模型）

// 解n元一次方程组Ax=b
void gauss(vector<vector<double>>& A, vector<double>& b) {int n = A.size();for (int i = 0; i < n; ++i) {// 选主元int maxr = i;for (int j = i+1; j < n; ++j) if (fabs(A[j][i]) > fabs(A[maxr][i])) maxr = j;swap(A[i], A[maxr]); swap(b[i], b[maxr]);// 消元double div = A[i][i];for (int j = i; j < n; ++j) A[i][j] /= div;b[i] /= div;for (int j = 0; j < n; ++j) if (j != i && fabs(A[j][i]) > 1e-12) {double mul = A[j][i];for (int k = i; k < n; ++k) A[j][k] -= mul * A[i][k];b[j] -= mul * b[i];}}
}

5. 典型应用场景

• 网格路径：$E[i][j]=1+p_{u}pE[i-1][j]+p_{d}ownE[i+1][j]+p_{l}eftE[i][j-1]+p_{r}ightE[i][j+1]$
• 博弈问题：先手取最大值，后手取最小值（如 $E=\max /min(\sum p_k{E}_k)$）
• 随机游走：数轴上左右移动，求到达边界的期望时间

四、避坑指南（常见错误解析）

1. 状态转移方向错误

正向遍历导致未计算的状态被访问（应逆向递推）。

// 错误示例（正向遍历导致数据污染）
for(int i=0; i<n; ++i) // ❌dp[i] = ... + dp[i+1];
// 正确写法（逆向遍历）
for(int i=n-1; i>=0; --i) // ✅dp[i] = ... + dp[i+1];

2. 边界条件遗漏

未处理终止状态（如 $E[n]=0$ 必须显式定义）。

// 必须显式处理的边界情况
if(pos == target return 0; // 终止条件
if(pos < 0 || pos >= n) return INF; // 无效状态

3. 概率未归一化

转移概率和不为 $1$ 时未除以总和（如 $dp[i]=p1E1+p2E2$ 需改为 $(p1E1+p2E2)/(p1+p2)$）。

// 错误概率计算
double p1 = 0.3, p2 = 0.3;
double E = p1*E1 + p2*E2; // ❌ 总概率0.6
// 正确处理
double E = (p1*E1 + p2*E2) / (p1+p2); // ✅

4. 调试技巧

• 状态可视化：打印 $dp[i]$ 的递推过程，检查转移是否符合预期。
• 收敛性检查：迭代更新时判断前后两次结果差是否小于 $1e-12$，确保算法收敛。

五、综合案例（完整代码）

题目：Codeforces 2183 - Expected XOR

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e5+9;double dp[N][2];
inlinre double solve(int pos, bool has_xor){if(pos == 0)  return has_xor ? 1.0 : 0.0;if(dp[pos][has_xor] >= 0)  return dp[pos][has_xor];double res = 0.0;//模拟两种操作的概率转移res += 0.5*solve(pos-1, has_xor^1);res += 0.5*solve(pos-1, has_xor);return dp[pos][has_xor] = res;
}
signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)int n;cin >> n;memset(dp, -1, sizeof(dp));cout << fixed << setprecision(10) << solve(n, false) << "\n";return 0;
}

随机游走问题

问题：质点从 $0$ 出发，每秒以 $0.5$ 概率左右移动，求首次到达 $+N$ 或 $-M$ 的期望时间。
状态转移：$E[i]=1+0.5E[i-1]+0.5E[i+1]$，边界 $E[N]=E[-M]=0$。
代码实现：

double dp[2005];
inline double dfs(int i){if(i == N || i == -M)  return 0;if(dp[i] >= 0)  return dp[i];return dp[i] = 1+0.5*dfs(i+1)+0.5*dfs(i-1);
}

六、训练路线（从入门到精通）

1. 基础阶段（3天）
   • 掌握线性无环模型（3道经典题）
   • 重点训练：骰子问题、随机游走
   • 工具：洛谷P1983、Codeforces Div2 B
2. 进阶阶段（5天）
   • 树形DP与环形DP（5道题）
   • 重点训练：树上的概率、高斯消元应用
   • 工具：AtCoder DP E、CSES 2183
3. 实战阶段（7天）
   • 综合题型训练（10道题）
   • 重点突破：期望最值、组合概率
   • 工具：Codeforces 1237E、AtCoder DP F

七、数学工具箱（进阶必备）

1. 生成函数法

//求解递推式 E[n] = pE[n+1] + qE[n-1]
生成函数 G(x) = Σ E[n]x^n
通过生成函数方程求解闭合式

2. 矩阵快速幂

//环形状态快速转移
struct Matrix{vector<vector<double>> mat;Matrix operator*(const Matrix& other){//实现矩阵乘法}
};

3. 蒙特卡洛验证

inline double monte_carlo(int trials){mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());double sum = 0;for(int i = 0; i < trials; ++i){sum += simulate(rng);}return sum/trials;
}

八、常见误区（认知误区解析）

1. “概率问题必须用DP”
   • 反例：对称性问题的数学解法（如赌徒破产问题）
   • 启示：先尝试数学方法，再考虑DP
2. “状态转移必须显式写出”
   • 反例：线性方程组直接求解（如环形问题）
   • 工具：Gauss-Jordan消元法（时间复杂度O(n^3)）
3. “期望问题必须精确计算”
   • 替代方案：蒙特卡洛+置信区间（适用于大状态空间）

九、学习资源（精选推荐）

1. 算法竞赛
   • 书籍：《概率与期望：算法竞赛指南》（Steven Halim）
   • 题库：Codeforces标签#probabilistic-dp（精选50题）
2. 数学理论
   • 论文：Markov Chain Monte Carlo（MCMC）基础
   • 在线课程：MIT 6.042J/18.062J（概率与线性代数）
3. 工程实践
   • 工具库：Boost.Random（高精度随机数生成）
   • 框架：TensorFlow Probability（概率编程）

十、扩展阅读（高级主题）

1. 马尔可夫链
   • 状态转移矩阵的构建与求解
2. 蒙特卡洛验证

   //生成随机样本验证期望值double monte_carlo(int trials){double sum = 0;for(int i = 0; i < trials; ++i){sum += simulate();}return sum/trials;}

3. 生成函数方法
   • 将递推式转换为生成函数进行解析求解

---

学习建议：

1. 每周保持3-5道相关题目训练
2. 重点突破高斯消元法和生成函数
3. 使用Valgrind检测概率计算中的精度问题
4. 建立错题本记录典型错误模式
   典型题单：

• P3232 [HNOI2013] 游走 //
• Codeforces 1237E（骰子爬楼梯）
• AtCoder DP E（树形随机游走）
• CSES 2183（期望XOR）
• 洛谷P8774（甲壳虫爬行问题）
• CF280C（盾牌选择问题）
  通过系统化训练，建议在3-4周内达到算法竞赛中概率期望DP问题的稳定AC水平。

---

1. 进阶步骤

• 手写推导简单问题（如骰子问题）的转移方程。
• 用调试工具观察状态转移过程。
• 将经典 DP 问题（如背包）改造为概率版本。
• 刷题训练：Codeforces 1237E、CSES 2183、AtCoder DP Contest E、洛谷 P1983。

2. 推荐资料

• 马尔可夫链与状态转移矩阵
• 蒙特卡洛模拟验证期望
• 生成函数与递推式解析求解
  通过系统掌握概率期望 DP，可将随机问题转化为确定性递推，结合数学推导与编程实践，逐步提升对概率建模和状态转移的敏感度。