引言
期望DP（Expected Value Dynamic Programming）是处理随机过程与概率决策问题的利器。从掷骰子到随机游走，从抽卡游戏到马尔可夫决策，凡是涉及”在随机事件下平均需要多少步/多少代价”的问题，都可用期望DP建模求解。本文将用Java实现多个经典的期望DP问题，深入讲解状态设计、转移方程构建与线性方程组求解。
期望DP的核心思想
期望DP与常规DP的本质区别：转移不是确定性的，而是概率加权的。对于状态 $i$，设以概率 $p_k$ 转移到状态 $s_k$ 并产生代价 $c_k$，则期望代价满足：
$$E[i] = \sum_{k} p_k \cdot (E[s_k] + c_k)$$
若 $i$ 可能以概率 $p_{self}$ 保持自身（如需要重试），则需整理方程：
$$E[i] = p_{self} \cdot (E[i] + c_{self}) + \sum_{k \neq self} p_k \cdot (E[s_k] + c_k)$$
$$E[i] = \frac{\sum_{k \neq self} p_k \cdot (E[s_k] + c_k) + p_{self} \cdot c_{self}}{1 – p_{self}}$$
例题一：骰子期望投掷次数
问题：一个六面骰子，平均需要投掷多少次才能看到所有六个面至少各一次？
状态设计：$dp[i]$ 表示已经看到 $i$ 个不同面，还需的期望投掷次数。
转移方程：当已看到 $i$ 个面时，下一次投掷：
– 以概率 $\frac{i}{6}$ 看到已有面，状态不变
– 以概率 $\frac{6-i}{6}$ 看到新面，状态转移到 $i+1$
$$dp[i] = 1 + \frac{i}{6} \cdot dp[i] + \frac{6-i}{6} \cdot dp[i+1]$$
整理得：
$$dp[i] = \frac{6 + (6-i) \cdot dp[i+1]}{6-i}$$
import java.util.*;
/**
* 期望DP核心算法实现
* 涵盖：骰子问题、随机游走、迷宫逃生等经典模型
*/
public class ExpectedValueDP {
/**
* 例题1：骰子集齐问题
* 六面骰子，求集齐所有面的期望投掷次数
* @param faces 骰子面数
* @return 期望投掷次数
*/
public static double diceCollectorExpectation(int faces) {
// dp[i] = 已收集i个面，还需的期望次数
double[] dp = new double[faces + 1];
dp[faces] = 0; // 全部集齐，还需0次
// 倒推：从faces-1到0
for (int i = faces - 1; i >= 0; i--) {
// dp[i] = 1 + (i/faces)*dp[i] + ((faces-i)/faces)*dp[i+1]
// 整理：dp[i] * (1 - i/faces) = 1 + (faces-i)/faces * dp[i+1]
// dp[i] = (faces + (faces-i) * dp[i+1]) / (faces - i)
dp[i] = (faces + (faces - i) * dp[i + 1]) / (faces - i);
}
return dp[0];
}
例题二：一维随机游走
问题：数轴上位置0到n，从位置k出发，每次以等概率向左或向右移动一步。到达0或n时停止。求从k出发到达n的期望步数。
状态设计：$dp[i]$ 表示从位置 $i$ 出发到达 $n$ 的期望步数。边界条件 $dp[0]=0$（已到达0但目标为n，可视为失败或重新定义），$dp[n]=0$。
更经典的问题：求到达边界（0或n）的期望步数。设 $dp[i]$ 为从 $i$ 出发到达任一边界的期望步数：
$$dp[i] = 1 + 0.5 \cdot dp[i-1] + 0.5 \cdot dp[i+1]$$
边界：$dp[0] = 0$，$dp[n] = 0$
/**
* 例题2：一维随机游走到达边界的期望步数
* @param n 右边界
* @param start 起始位置
* @return 期望步数
*/
public static double randomWalkBoundary(int n, int start) {
// dp[i] = 从i出发到达0或n的期望步数
// dp[i] = 1 + 0.5*dp[i-1] + 0.5*dp[i+1]
// 整理：dp[i+1] - 2*dp[i] + dp[i-1] = -2
// 这是二阶线性递推，通解为 dp[i] = -i^2 + A*i + B
// 代入边界 dp[0]=0, dp[n]=0 得 dp[i] = i*(n-i)
// 用DP数值验证通解
double[] dp = new double[n + 1];
dp[0] = 0;
dp[n] = 0;
// 高斯-赛德尔迭代求解线性方程组
// 由于精确解是二次的，迭代收敛很快
for (int iter = 0; iter < 10000; iter++) {
double maxDiff = 0;
for (int i = 1; i < n; i++) {
double newVal = 1 + 0.5 * dp[i - 1] + 0.5 * dp[i + 1];
maxDiff = Math.max(maxDiff, Math.abs(newVal - dp[i]));
dp[i] = newVal;
}
if (maxDiff < 1e-12) break;
}
return dp[start];
}
/**
* 随机游走精确解：dp[i] = i * (n - i)
*/
public static double randomWalkExact(int n, int start) {
return (double) start * (n - start);
}
例题三：迷宫逃生期望时间
问题：给定一个包含通道和陷阱的迷宫，每个位置有若干出口，选择每个出口有一定概率。求从起点到达出口的期望时间。
/**
* 例题3：迷宫逃生期望时间
* @param n 节点数（0为起点，n-1为出口）
* @param edges 邻接表：edges[i] = List of {邻居, 通过时间}
* @return 从起点到达出口的期望时间
*/
public static double mazeEscapeExpectation(
int n,
List<int[]>[] edges) {
// dp[i] = 从节点i到达出口的期望时间
double[] dp = new double[n];
dp[n - 1] = 0; // 出口期望为0
// 拓扑序处理：若图为DAG可直接递推
// 一般图需要使用高斯消元或迭代法
boolean[] visited = new boolean[n];
Arrays.fill(visited, false);
visited[n - 1] = true;
// 迭代法（适用于无环或收敛的情况）
for (int iter = 0; iter < 100000; iter++) {
double maxDiff = 0;
for (int i = n - 2; i >= 0; i--) {
if (edges[i] == null || edges[i].isEmpty()) continue;
double newVal = 0;
double prob = 1.0 / edges[i].size();
for (int[] e : edges[i]) {
int to = e[0];
int time = e[1];
// 若to已访问（即dp[to]已知），直接加
// 否则使用当前估计值
newVal += prob * (time + dp[to]);
}
maxDiff = Math.max(maxDiff, Math.abs(newVal - dp[i]));
dp[i] = newVal;
}
if (maxDiff < 1e-12) break;
}
return dp[0];
}
例题四：抽卡期望与有保底机制
问题：卡池中有n张不同的卡，每次抽卡等概率获得一张。求集齐所有卡的期望抽卡次数。进阶：加入保底机制——每k次必出未拥有的卡。
/**
* 例题4：抽卡集齐期望（优惠券收集问题）
* @param n 卡牌总数
* @return 集齐所有卡的期望抽卡次数
*/
public static double cardCollectionExpectation(int n) {
// dp[i] = 已收集i张，还需的期望次数
// 每次抽到已有卡的概率 i/n，新卡概率 (n-i)/n
// dp[i] = 1 + (i/n)*dp[i] + ((n-i)/n)*dp[i+1]
// 整理得 dp[i] = (n + (n-i)*dp[i+1]) / (n-i)
double[] dp = new double[n + 1];
dp[n] = 0;
for (int i = n - 1; i >= 0; i--) {
dp[i] = (n + (n - i) * dp[i + 1]) / (n - i);
}
return dp[0];
}
/**
* 带保底的抽卡：每k抽必出新卡
* @param n 卡牌总数
* @param k 保底间隔
* @return 期望抽卡次数
*/
public static double cardCollectionWithPity(int n, int k) {
// 状态：dp[i][j] = 已收集i张，距离上次出新卡已抽了j次
// 复杂度O(n*k)，适合中小规模
double[][] dp = new double[n + 1][k + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], 0);
}
// 倒推
for (int i = n - 1; i >= 0; i--) {
for (int j = k - 1; j >= 0; j--) {
double pOld = (double) i / n; // 抽到已有卡的概率
double pNew = (double) (n - i) / n; // 抽到新卡的概率
if (j + 1 == k) {
// 下次必出保底（新卡）
dp[i][j] = 1 + dp[i + 1][0];
} else {
// 正常概率
dp[i][j] = 1 + pOld * dp[i][j + 1] + pNew * dp[i + 1][0];
}
}
}
return dp[0][0];
}
例题五：赌徒破产问题
问题：赌徒初始有 $i$ 元，每局以概率 $p$ 赢1元，以概率 $q=1-p$ 输1元。达到 $n$ 元目标或破产（0元）时停止。求达到目标的概率和期望局数。
/**
* 例题5：赌徒破产问题
* @param n 目标金额
* @param start 初始金额
* @param p 每局获胜概率
* @return double[2]：{达到目标的概率, 期望局数}
*/
public static double[] gamblerRuin(int n, int start, double p) {
double q = 1 - p;
// winProb[i] = 从i元达到n元的概率
double[] winProb = new double[n + 1];
winProb[0] = 0;
winProb[n] = 1;
if (Math.abs(p - q) < 1e-12) {
// p = q = 0.5 的特殊情况
for (int i = 1; i < n; i++) {
winProb[i] = (double) i / n;
}
} else {
// 通解：winProb[i] = (1 - (q/p)^i) / (1 - (q/p)^n)
double ratio = q / p;
double denom = 1 - Math.pow(ratio, n);
for (int i = 1; i < n; i++) {
winProb[i] = (1 - Math.pow(ratio, i)) / denom;
}
}
// expected[i] = 从i元到达边界的期望局数
double[] expected = new double[n + 1];
expected[0] = 0;
expected[n] = 0;
// 迭代求解
for (int iter = 0; iter < 100000; iter++) {
double maxDiff = 0;
for (int i = 1; i < n; i++) {
double newVal = 1 + p * expected[i + 1] + q * expected[i - 1];
maxDiff = Math.max(maxDiff, Math.abs(newVal - expected[i]));
expected[i] = newVal;
}
if (maxDiff < 1e-12) break;
}
return new double[]{winProb[start], expected[start]};
}
高斯消元求解一般期望DP
当状态转移形成环（非DAG）时，需要建立线性方程组并用高斯消元求解。
/**
* 使用高斯消元求解一般期望DP线性方程组
* 方程形式：E[i] = sum(p[i][j] * (E[j] + cost[i][j]))
* 整理为：E[i] - sum(p[i][j] * E[j]) = sum(p[i][j] * cost[i][j])
*
* @param n 状态数
* @param transitions 转移矩阵：transitions[i] = List of {to, prob, cost}
* @param terminal 终止状态标记
* @return 各状态的期望值
*/
public static double[] solveByGaussianElimination(
int n,
List<double[]>[] transitions,
boolean[] terminal) {
// 构建增广矩阵 A * E = B
double[][] A = new double[n][n];
double[] B = new double[n];
for (int i = 0; i < n; i++) {
if (terminal[i]) {
A[i][i] = 1;
B[i] = 0;
continue;
}
A[i][i] = 1;
for (double[] trans : transitions[i]) {
int to = (int) trans[0];
double prob = trans[1];
double cost = trans[2];
A[i][to] -= prob;
B[i] += prob * cost;
}
}
// 高斯消元（部分主元）
for (int col = 0; col < n; col++) {
// 找主元
int pivot = col;
for (int row = col + 1; row < n; row++) {
if (Math.abs(A[row][col]) > Math.abs(A[pivot][col])) {
pivot = row;
}
}
// 交换行
double[] tempA = A[col];
A[col] = A[pivot];
A[pivot] = tempA;
double tempB = B[col];
B[col] = B[pivot];
B[pivot] = tempB;
// 消元
for (int row = col + 1; row < n; row++) {
double factor = A[row][col] / A[col][col];
for (int c = col; c < n; c++) {
A[row][c] -= factor * A[col][c];
}
B[row] -= factor * B[col];
}
}
// 回代
double[] E = new double[n];
for (int i = n - 1; i >= 0; i--) {
double sum = B[i];
for (int j = i + 1; j < n; j++) {
sum -= A[i][j] * E[j];
}
E[i] = sum / A[i][i];
}
return E;
}
完整测试程序
public static void main(String[] args) {
System.out.println("=== 期望DP测试 ===\n");
// 测试1：骰子集齐
System.out.println("测试1：六面骰子集齐期望次数");
double diceExp = diceCollectorExpectation(6);
System.out.printf(" 结果: %.6f%n", diceExp);
System.out.printf(" 理论值: %.6f (调和数 H6 * 6)%n%n", 6 * (1 + 0.5 + 1.0/3 + 0.25 + 0.2 + 1.0/6));
// 测试2：随机游走
System.out.println("测试2：一维随机游走 (n=10, start=5)");
double walkExp = randomWalkBoundary(10, 5);
double walkExact = randomWalkExact(10, 5);
System.out.printf(" 迭代解: %.6f%n", walkExp);
System.out.printf(" 精确解: %.6f%n%n", walkExact);
// 测试3：抽卡集齐
System.out.println("测试3：抽卡集齐期望 (n=5张卡)");
double cardExp = cardCollectionExpectation(5);
System.out.printf(" 无保底期望: %.6f%n", cardExp);
double cardPity = cardCollectionWithPity(5, 3);
System.out.printf(" 每3抽保底期望: %.6f%n%n", cardPity);
// 测试4：赌徒破产
System.out.println("测试4：赌徒破产 (n=10, start=5, p=0.5)");
double[] gambler = gamblerRuin(10, 5, 0.5);
System.out.printf(" 达到目标概率: %.6f%n", gambler[0]);
System.out.printf(" 期望局数: %.6f%n%n", gambler[1]);
// 测试5：高斯消元求解
System.out.println("测试5：高斯消元验证赌徒破产");
int gn = 11;
@SuppressWarnings("unchecked")
List<double[]>[] trans = new ArrayList[gn];
for (int i = 0; i < gn; i++) {
trans[i] = new ArrayList<>();
}
boolean[] term = new boolean[gn];
term[0] = true;
term[10] = true;
for (int i = 1; i < 10; i++) {
trans[i].add(new double[]{i - 1, 0.5, 1});
trans[i].add(new double[]{i + 1, 0.5, 1});
}
double[] gaussResult = solveByGaussianElimination(gn, trans, term);
System.out.printf(" 从5元出发期望局数(高斯消元): %.6f%n", gaussResult[5]);
System.out.printf(" 从5元出发期望局数(迭代法): %.6f%n%n", gambler[1]);
System.out.println("所有测试完成！");
}
}
期望DP的状态设计技巧
- 逆向思维：从终止状态倒推，终止状态的期望通常为0
- 加一法则：每次转移天然包含”执行本次操作”的1单位代价
- 自环处理：以概率 $p$ 保持当前状态时，需移项整理方程
- 方程组视角：复杂状态关系用线性方程组统一求解
复杂度分析
| 问题类型 | 状态数 | 时间复杂度 | 求解方法 |
|---|---|---|---|
| DAG型期望DP | $O(n)$ | $O(n)$ | 拓扑序递推 |
| 树型期望DP | $O(n)$ | $O(n)$ | DFS后序遍历 |
| 一般图迭代 | $O(n)$ | $O(n \cdot iter)$ | 高斯-赛德尔迭代 |
| 一般图精确 | $O(n)$ | $O(n^3)$ | 高斯消元 |
总结
期望DP将概率论与动态规划巧妙结合，核心在于正确建立”期望 = 概率加权后继期望 + 当前代价”的转移方程。Java实现中需特别注意浮点精度问题——涉及金钱或精确比较时建议使用 double 并设置合理的容差。对于带环的复杂状态转移，高斯消元提供了通用的精确解法，而迭代法则在稀疏图上往往更高效。掌握期望DP后，从游戏策划中的抽卡概率设计到金融工程中的随机模型分析，都将有坚实的算法基础。
