一、算法概述
概率动态规划（Probabilistic Dynamic Programming），简称概率 DP，是动态规划在概率含数学应用领域的延伸。它用于求解带有随机性的过程中的最优化或期望类问题，例如”在随机走步中到达某状态的期望步数”、”投掷骰子到达目标状态的期望次数”、”博弈中先手的胜率/期望收益”等。概率 DP 的核心是用动态规划的状态表示期望值或概率分布，并通过状态转移方程把这些期望逐步推导出来。
概率 DP 与确定性 DP 的区别在于：
1. 状态不再是”最大/最小收益”这样的标量，而是 期望值（带权平均）；
2. 状态转移方程中会出现期望的线性组合：从一个状态出发的下一步可能是多种结果，我们要把所有结果的期望按概率加权求和；
3. 题目经常要求”无穷次操作后的稳态期望”，这时需要解线性方程组，或者使用”反向递推 + 高斯消元”。
本文将系统介绍概率 DP 的几个经典模型：线性期望 DP、马尔可夫链稳态、博弈概率、几何分布等，并通过完整 Java 代码演示”投硬币正面累计期望次数”和”随机游走期望步数”两个经典问题。
二、算法原理
2.1 期望的线性性
设一个随机变量 X 可以分解为一系列相互独立或条件独立的随机变量，则：
$$E[X] = \sum_i E[X_i]$$
这是概率 DP 中最重要的工具。在动态规划中，我们经常把”到达终点的期望步数”分解为”每一步的贡献之和”，每一步贡献的期望是确定的。例如在一条长度为 n 的路径上随机前进一步，每步成功概率为 p，则期望步数为 1/p。
2.2 反向递推 vs 正向递推
在确定性 DP 中，我们经常用”从初始状态出发，正向递推到目标状态”的方式求解。但在概率 DP 中，反向递推（从目标状态反推到初始状态）通常更自然。
为什么？因为我们想要求的是”从状态 S 出发到达终点的期望”，而状态转移是”从 S 出发，下一步以概率 p 到达 S1，以概率 1-p 到达 S2，……”。如果正向递推，需要解一个无穷状态空间的递推；反向递推则可以写成：
$$E[S] = 1 + \sum_i p_i \cdot E[S_i]$$
这个公式给出了一个线性方程。当状态有限时，我们可以用高斯消元在 O(n^3) 内求解；当状态是”线性排列”或”简单链式”时，可以从前向后直接递推。
2.3 高斯消元法
当状态转移图是一个有环的图时（这在概率 DP 中很常见，例如带”复活”的随机过程），单纯递推无法收敛，必须用高斯消元。
设有 n 个未知数 E[1], E[2], ..., E[n]，每个状态有：
$$E[i] = c_i + \sum_j a_{ij} E[j]$$
整理成矩阵形式 A * E = b，用标准的高斯消元求解即可。复杂度 O(n^3)，对于 n ≤ 500 是可接受的。
2.4 经典模型
2.4.1 几何分布期望
反复尝试某操作，单次成功概率为 p，求期望尝试次数。答案为 1/p。
2.4.2 随机游走
在数轴 [0, n] 上，状态 i 以概率 p 走到 i+1、以概率 1-p 走到 i-1，求从 i 出发到达 0 或 n 的期望步数。可建立方程组：
E[0] = E[n] = 0
E[i] = 1 + p * E[i+1] + (1-p) * E[i-1] (0 < i < n)
直接高斯消元即可。
2.4.3 博弈概率
两个选手博弈，每回合以一定概率分胜负，求”先手获胜的概率”。通常使用反向递推：设 P[i] 为”在状态 i 先手获胜的概率”，则：
$$P[i] = \sum_{a \in actions(i)} p(a) \cdot WinProb(next(i, a))$$
其中 next(i, a) 是执行操作 a 后到达的状态。这种递推在状态空间为 DAG 时容易做；带环时仍需要解方程。
2.5 期望与方差
很多概率 DP 题目要求同时求期望与方差。设当前状态为 dp[i]，下一步以概率 p_j 转移到 dp[j]，新增收益 c，则：
dp'[i] = c + sum_j p_j * dp[j] (期望)
var[i] = sum_j p_j * (dp[j] - dp'[i])^2 (方差)
方差通常通过二阶矩（平方期望）来求：E[X^2] = sum_j p_j * (dp[j] + c)^2。
三、Java 实现
我们实现两个经典模型：
- 线性期望 DP（投硬币正面累计）：投一枚均匀硬币，直到累计出现 k 次正面为止，求期望投掷次数。公式为
2k - 1（由几何分布推导）。 - 带边界的随机游走：在 [0, n] 上以概率 p 向右、1-p 向左移动，求从位置 i 出发到达任一边界的期望步数；用高斯消元求解。
import java.util.Scanner;
/**
* 概率 DP —— 期望计算
*
* 本示例实现两个经典模型：
* 1) 累计正面次数达到 K 的期望投掷数
* 2) 区间随机游走的期望首达时间（高斯消元法）
*/
public class ProbabilityDP {
// ============================================================
// 1) 投掷均匀硬币，直到出现 K 次正面为止，求期望投掷次数
// 解析解为 2K - 1（由几何分布 + 负二项分布推导）
// 这里我们用 DP 反向递推验证：E[k] = 1 + (E[k+1] + E[k])/2
// 解得 E[0] = 2K - 1
// ============================================================
public static double coinUntilKHeads(int K) {
double[] dp = new double[K + 1];
// 反向递推
// E[k] = 1 + (1/2) * E[k+1] + (1/2) * E[k]
// 移项：E[k] - (1/2) * E[k] = 1 + (1/2) * E[k+1]
// E[k] = (1 + E[k+1] / 2) * 2 = 2 + E[k+1]
// 终止条件：E[K] = 0
dp[K] = 0;
for (int k = K - 1; k >= 0; k--) {
dp[k] = 2.0 + dp[k + 1];
}
return dp[0];
}
// ============================================================
// 2) 区间随机游走 [0, n]：状态 i（0 < i < n）以概率 p 转移到 i+1，
// 以概率 1-p 转移到 i-1。E[0] = E[n] = 0。
// 内部状态 i=1..n-1 的方程：
// E[i] = 1 + p * E[i+1] + (1-p) * E[i-1]
// 重写为：
// -(1-p) * E[i-1] + 1 * E[i] - p * E[i+1] = 1
// 用高斯消元求解 n-1 个未知数。
// ============================================================
/**
* 求解随机游走期望
* @param n 区间右边界
* @param p 向右移动的概率
* @return dp[1..n-1] 的期望首达时间
*/
public static double[] randomWalkExpectation(int n, double p) {
if (n <= 1) return new double[0];
int m = n - 1; // 未知数个数：E[1]..E[n-1]
// 构造增广矩阵：A * E = b，A 是 m x m 的，b 是 m x 1
double[][] A = new double[m][m];
double[] b = new double[m];
for (int i = 0; i < m; i++) {
// 内部状态 i+1
A[i][i] = 1.0;
if (i - 1 >= 0) {
A[i][i - 1] = -(1 - p);
}
if (i + 1 < m) {
A[i][i + 1] = -p;
}
b[i] = 1.0;
}
// 高斯消元
gaussian(A, b);
return b; // 消元后 b 中即为 E[1..n-1]
}
/**
* 标准的高斯消元（部分主元），原地修改矩阵 A 与向量 b
*/
private static void gaussian(double[][] A, double[] b) {
int n = b.length;
for (int k = 0; k < n; k++) {
// 选主元：找绝对值最大的行
int pivot = k;
double maxVal = Math.abs(A[k][k]);
for (int i = k + 1; i < n; i++) {
if (Math.abs(A[i][k]) > maxVal) {
maxVal = Math.abs(A[i][k]);
pivot = i;
}
}
if (maxVal < 1e-12) {
throw new IllegalStateException("矩阵奇异，无唯一解");
}
// 交换行
if (pivot != k) {
double[] tmp = A[k]; A[k] = A[pivot]; A[pivot] = tmp;
double tb = b[k]; b[k] = b[pivot]; b[pivot] = tb;
}
// 消元
for (int i = k + 1; i < n; i++) {
double factor = A[i][k] / A[k][k];
if (Math.abs(factor) < 1e-15) continue;
for (int j = k; j < n; j++) {
A[i][j] -= factor * A[k][j];
}
b[i] -= factor * b[k];
}
}
// 回代
for (int i = n - 1; i >= 0; i--) {
double sum = b[i];
for (int j = i + 1; j < n; j++) {
sum -= A[i][j] * b[j];
}
b[i] = sum / A[i][i];
}
}
// ============================================================
// 3) 经典"期望递增次数"问题：
// 有一个骰子，每次掷出 1-6（均匀）。
// 如果当前点数 < k，下一轮点数 = max(当前, 掷出)；否则停止。
// 求从点数 0 到达 ≥ k 的期望步数。
// 这是简化的"升级"模型。
// ============================================================
public static double diceUpgradeExpectation(int k) {
// 状态 i 表示当前点数 ∈ [0, k-1]
// E[i] = 1 + (1/6) * sum_{v=1..6} E[max(i, v)]
// E[k-1] = 1 + (1/6) * sum_{v=1..6} E[max(k-1, v)] = 1 + (1/6) * sum E[v] (v ≥ k-1)
// ...用反向递推
if (k == 0) return 0;
double[] E = new double[k];
// 反向递推
for (int i = k - 1; i >= 0; i--) {
double sum = 0;
for (int v = 1; v <= 6; v++) {
int next = Math.max(i, v);
if (next >= k) {
// 终止态（≥ k）
sum += 0;
} else {
sum += E[next];
}
}
E[i] = 1.0 + sum / 6.0;
}
return E[0];
}
// ================== 演示入口 ==================
public static void main(String[] args) {
// 1) 投硬币累计 K 次正面
int K = 5;
System.out.println("投硬币累计 " + K + " 次正面的期望投掷数：" + coinUntilKHeads(K));
// 2) 随机游走
int n = 10;
double p = 0.5;
double[] E = randomWalkExpectation(n, p);
System.out.println("区间 [0, " + n + "] 上的随机游走期望首达时间（p=" + p + "）：");
for (int i = 1; i < n; i++) {
System.out.println(" E[" + i + "] = " + E[i - 1]);
}
// 3) 骰子升级
int target = 4;
System.out.println("骰子升级到 ≥ " + target + " 的期望步数：" + diceUpgradeExpectation(target));
}
}
3.1 代码解读
coinUntilKHeads：用反向递推求解”投出 K 次正面”的期望次数。最终答案等于 2K-1（验证用）。randomWalkExpectation：建立n-1个未知数的线性方程组，用部分主元的高斯消元在 O(n³) 内求解。这是处理”带边界随机游走”问题的经典做法。diceUpgradeExpectation：反向递推，每一步把”未来期望”按概率加权求和。注意终止态的处理——当next >= k时期望贡献为 0。gaussian：标准部分主元高斯消元，确保数值稳定性。
四、复杂度分析
4.1 时间复杂度
| 模型 | 复杂度 |
|---|---|
| 线性递推（无环） | O(n) |
| 随机游走 + 高斯消元 | O(n³) |
| 博弈概率（DAG） | O(n + m) |
| 博弈概率（带环） | O(n³) 或迭代法 O(n² · log precision) |
4.2 空间复杂度
- 反向递推：O(n)；
- 高斯消元：O(n²)（用于矩阵存储）；
- 配合滚动数组可以压缩到 O(n)。
4.3 数值精度
浮点数运算是概率 DP 的常见坑。建议：
– 多次操作时使用 double 即可，但比较”两个期望是否相等”时要小心精度（建议设置 eps = 1e-9）；
– 高斯消元尽量使用部分主元（避免除以小量）；
– 对”概率恰为 0/1″的情况要单独处理（用整数 DP）。
五、应用场景
5.1 算法竞赛
概率 DP 是竞赛中的高频考点。常见的题型有：
– 数学期望题：求随机过程的期望步数、期望收益、期望最大/最小值；
– 概率计数题：求达到某状态的概率分布；
– 博弈题：求先手胜率、平局率、必败状态；
– 停止问题：求某事件首次发生的期望时间。
5.2 马尔可夫链
在数学建模、机器学习中常常需要计算一个马尔可夫链的稳态分布。这就是概率 DP 中”无限状态递推 + 高斯消元”的典型应用。PageRank 算法就是建立在马尔可夫链稳态之上的。
5.3 排队论
排队论中”平均等待时间”、”平均队列长度”等指标都可以通过概率 DP 求解。M/M/1 排队模型的解析解正是用差分方程（连续时间版本的概率 DP）推出的。
5.4 蒙特卡洛与机器学习
在强化学习（Reinforcement Learning）中，”状态价值函数 V(s)”就是满足 Bellman 方程的期望函数：
$$V(s) = \sum_a \pi(a|s) [R(s, a) + \gamma \sum_{s’} P(s’|s,a) V(s’)]$$
这正是概率 DP 的扩展形式。
5.5 注意事项
- 一定要明确终止态：避免无穷递推；
- 仔细处理边界条件：例如
E[0] = 0、E[n] = 0； - 状态设计：让状态转移只与”上一两步”或”当前状态”有关，避免复杂的依赖；
- 高斯消元慎用：当 n 很大（如 10000+）时不可行，需要考虑迭代法或稀疏矩阵求解器。
六、总结
概率 DP 是处理随机过程最优化问题的核心方法。它把动态规划的”分阶段决策”思想延伸到期望与概率维度，并通过”反向递推”或”高斯消元”两种主要方式求解。本文给出的两个示例代码——投硬币累计正面、随机游走首达时间——是竞赛中最基础的两个概率 DP 模型，熟练掌握后可以自然推广到更复杂的问题中。
学习概率 DP 的关键在于：
1. 清晰定义状态：包括”在哪个状态”和”已经消耗了多少资源”；
2. 正确写出转移方程：明确每一步的”贡献（cost）”和”下一步状态的概率分布”；
3. 选择求解方式：递推 vs 高斯消元 vs 迭代法；
4. 重视精度：浮点运算的误差会累积，需要合理设置容差。
希望本文能帮助你在实际比赛中快速、准确地建立概率 DP 模型。
