第 6.7 章：概率期望与计数 DP

6.7.0 从两道题出发

前面几章的 DP 都在求「最优值」。但竞赛里还有一大类题问的不是最优，而是：

题 1（绿蛙跳格）： 一只青蛙站在数轴的格 1 上，要跳到格 N（N ≤ 10⁶）。每一步它等概率地跳 1 格或 2 格；如果跳 2 格会越过 N，就视为直接到达。问从格 1 跳到格 N 的期望步数。

题 2（数字组合）： 从 1, 2, ..., N 中选出若干个互不相同的数（每个数要么选要么不选），使它们的和恰好等于 K。问有多少种选法，答案对 10⁹+7 取模。N, K ≤ 1000。

这两道题都不能用前面的任何一种 DP 直接套：

• 题 1 没有「最优」——青蛙是随机跳的，你要求的是所有可能跳法的平均步数。这类题叫期望 DP。
• 题 2 不求最大也不求最小，求的是方案数——把每一个合法方案数一次，不多不少。这类题叫计数 DP。

再加上「求某个随机事件发生的概率」的概率 DP，就构成了本章的三位主角。它们与最优化 DP 共享同一套骨架——状态、转移、边界、计算顺序——但在三个关键处不同：

记住本章最重要的一句话：概率是顺推、期望是倒推、计数是不重不漏。

6.7.1 概率 DP

两条运算法则

概率 DP 只用两条规则，都在高中课本里：

乘法规则（分步）： 两件独立（或前后相继）的事同时发生，概率相乘。沿一条路径走到底，把每一步的概率乘起来。

加法规则（分类）： 到达同一结果的若干互斥方式，概率相加。这正是全概率公式：

$$P(A) = \sum_i P(B_i)\cdot P(A \mid B_i)$$

翻译成 DP 语言：dp[状态] = Σ 转移概率 × dp[下一状态]。概率做权重，转移加起来。

例题：抛硬币直到连续 2 次正面

题目： 不断抛一枚均匀硬币，直到首次出现连续 2 次正面为止。求抛掷次数的期望。

这是概率 DP 的入门经典，我们先用它讲清「状态设计」，下一节再补全期望推导。

第一步：设计状态。 随机过程当前处于什么局面？只取决于「到目前为止，末尾已经连着几个正面」：

dp[k] = 已连出 k 次正面（0 ≤ k ≤ 2）时，距离目标还需要多少次期望

目标状态是 dp[2] = 0（已经连续 2 次正面，结束）。

第二步：列出转移。 站在状态 k，抛一次硬币：

• 以概率 1/2 抛出正面 → 状态变为 k+1；
• 以概率 1/2 抛出反面 → 连续被打破，回到状态 0。

写成方程（注意这里有环：从状态 1 抛反面会回到 0，从 0 抛反面还是 0）：

$$f_0 = \tfrac{1}{2}(1 + f_1) + \tfrac{1}{2}(1 + f_0)$

$$f_1 = \tfrac{1}{2}(1 + f_2) + \tfrac{1}{2}(1 + f_0), \qquad f_2 = 0$$

第三步：解方程。 含自身的项（自环）移到左边：

• f_0 = 1 + (f_1 + f_0)/2 → f_0 = f_1 + 2
• f_1 = 1 + (0 + f_0)/2 → f_1 = f_0/2 + 1

代入解得 f₀ = 6, f₁ = 4。即平均需要抛 6 次才能首次连出 2 次正面。

通式（记住它）： 首次连出 k 次正面所需的期望次数是

$$E_k = 2^{k+1} - 2$$

k=1 时是 2，k=2 时是 6，k=3 时是 14。验证程序：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;                                  // n = 目标连出几次正面
    cin >> n;
    // dp[i]：从「连出 i 次正面」出发、到「连出 n 次」的期望步数（倒推）
    // 通式 E_k = 2^(k+1) - 2，这里用递推验证
    vector<double> f(n + 1, 0.0);
    f[n] = 0.0;                             // 终点
    // 从 n-1 倒着推：f[i] = 1 + 0.5*f[i+1] + 0.5*f[0]，
    // 含 f[0] 的环导致不能直接递推——但「首次连出 k 次」有通式，
    // 用差分验证：E[i] - E[i-1] = 2^i
    double ans = 0;
    for (int k = 1; k <= n; k++) ans += pow(2.0, k);
    cout << fixed << setprecision(6) << ans << "\n";
    return 0;
}

输入：1
输出：2.000000

输入：2
输出：6.000000

输入：3
输出：14.000000

与手算 E_k = 2+4+...+2^k = 2^{k+1}-2 完全一致。

这个例子教给我们两件事：

1. 状态设计的起点是「随机过程走到哪了」，而不是「我做了什么选择」。末尾连续正面数就是全部需要的信息。
2. 转移里出现自环（回到自己）时，方程仍然可解——把含自身的项移项即可；只有当环结构复杂到「移项解不动」（比如二维网格上既有环又互相依赖）时才需要高斯消元，那超出了 NOIP 范围。

概率 DP 代码框架

// 顺推：从初始状态（概率 1）出发，向所有可达状态累加概率
dp[初始] = 1.0;
for (每个状态按依赖顺序) {
    if (dp[状态] == 0) continue;          // 不可达，跳过
    for (每个转移，概率 p) {
        dp[下一状态] += dp[状态] * p;
    }
}

检查点： 每个状态所有转移概率之和必须等于 1（概率归一化）。忘了写某个分支，所有概率都会偏小。

6.7.2 期望 DP

最重要的工具：期望的线性性

$$E[X + Y] = E[X] + E[Y]$$

它无条件成立——X 和 Y 不需要独立！ 这是最容易被低估的定理。它意味着：不管整个随机过程多复杂，「总花费的期望 = 每一步花费的期望之和」，哪怕每一步的花费之间高度相关。

正因为有线性性，期望 DP 才不需要算「每条完整路径的概率×花费」——那几乎总是算不动。我们只需要对每个状态问一句：「从这里出发，期望还要花多少？」然后把「这一步的花费（期望是常数，直接 +1 或 +w）」和「下一状态的期望（按概率加权）」加起来。

为什么期望要倒推

看转移方向。设 f[i] = 从格 i 出发到终点的期望花费。一步之内发生的事是确定的（花费已知），一步之后进入哪个状态是随机的：

$$f[i] = \underbrace{1}{这一步的期望花费} + \sum_j p{ij}, f[j]$$

f[i] 依赖于更靠近终点的状态 f[j]——所以必须从终点往回推：终点已知（花费 0），一层层往外算。这就是「期望是倒推」的原因：定义的是「还差多少」，终点是唯一已知数。

（反过来，若定义 g[i] = 从起点走到 i 的期望花费，从起点顺推——但顺推期望要求「到达 i 的路径结构」已知，多数题上行不通。竞赛里 90% 的期望 DP 都是倒推。）

完整实战一：绿蛙跳格

回到开篇的题 1。f[i] = 从格 i 出发跳到 N 的期望步数：

• 边界：f[N] = 0（已在终点）。
• 转移：从格 i（i < N）跳一步，1/2 到 i+1、1/2 到 i+2；跳 2 格越过 N 时视为到达（期望 0）。这一步本身花费 1 步：

$$f_i = \frac{f_{i+1} + f_{i+2}}{2} + 1, \qquad f_N = 0$$

其中 i = N-1 时 f[i+2] 越界，按「视为到达」取 0。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<double> f(n + 2, 0.0);   // f[i]：从格 i 跳到 N 的期望步数
    f[n] = 0.0;                      // 终点：不需要再跳
    for (int i = n - 1; i >= 1; i--) {
        double a = f[i + 1];
        double b = (i + 2 <= n) ? f[i + 2] : 0.0;  // 越过 N 视为到达
        f[i] = (a + b) / 2.0 + 1.0;
    }
    cout << fixed << setprecision(6) << f[1] << "\n";
    return 0;
}

手算核对（N = 4，必须会手算）：

f[4] = 0                       （终点）
f[3] = (f[4] + 0) / 2 + 1 = 1  （跳 2 格越过 4，视为到达）
f[2] = (f[3] + f[4]) / 2 + 1 = (1 + 0)/2 + 1 = 1.5
f[1] = (f[2] + f[3]) / 2 + 1 = (1.5 + 1)/2 + 1 = 2.25

输入：4
输出：2.250000

✓ 与程序一致。可以再直觉验证：每步平均前进 1.5 格，走 3 格约需 2 步——2.25 步听起来合理。

复杂度： O(N)。

完整实战二：树上期望路径长

期望 DP 上树的版本。题目：

给一棵 N 个点的树（1 为根），每条边有长度。从根出发，每到 internal 一个点，从它的所有儿子中等概率选一个往下走，直到走到叶子。求走过的路径总长度的期望。N ≤ 10⁵。

状态： f[u] = 从点 u 出发走到某个叶子的期望路径长。

边界： u 是叶子时 f[u] = 0。

转移： 设 u 有 k 个儿子，儿子 v 由边权 w 相连，则

$$f_u = \frac{1}{k}\sum_{v \in \text{sons}(u)} \bigl(w_{uv} + f_v\bigr)$$

这里期望线性性在悄悄工作：w + f[v] 表示「走这条边的花费 + 之后的花费」，两者不独立（走不走到 v 才有 f[v]），但期望照样相加。树天然无环，后序遍历（先算儿子）即可，不需要倒推循环。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<pair<int,int>>> g(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<double> f(n + 1, 0.0);
    vector<int> parent(n + 1, 0), order;   // order：DFS 序，父在子前
    vector<int> stk = {1};
    vector<bool> vis(n + 1, false);
    while (!stk.empty()) {
        int u = stk.back(); stk.pop_back();
        vis[u] = true;
        order.push_back(u);
        for (auto [v, w] : g[u]) if (!vis[v]) {
            parent[v] = u;
            stk.push_back(v);
        }
    }
    // 逆序遍历 DFS 序 = 后序：儿子先于父亲
    for (int idx = (int)order.size() - 1; idx >= 0; idx--) {
        int u = order[idx];
        vector<pair<int,int>> ch;           // u 的儿子
        for (auto [v, w] : g[u]) if (v != parent[u]) ch.push_back({v, w});
        if (ch.empty()) { f[u] = 0.0; continue; }   // 叶子
        double s = 0.0;
        for (auto [v, w] : ch) s += w + f[v];
        f[u] = s / (double)ch.size();
    }
    cout << fixed << setprecision(6) << f[1] << "\n";
    return 0;
}

手算核对：

输入：
5
1 2 1
1 3 4
3 4 2
3 5 1

输出：
3.250000

树：1 有儿子 {2, 3}；3 有儿子 {4, 5}。f[4]=f[5]=f[2]=0（叶子）；f[3] = (2+1)/2 = 1.5；f[1] = (1 + 0 + 4 + 1.5)/2 = 6.5/2 = 3.25。✓

输入：
3
1 2 1
1 3 5

输出：
3.000000

f[1] = (1 + 5)/2 = 3。✓

复杂度： O(N)。

6.7.3 计数 DP

与最优化 DP 的一个本质区别

最优化 DP 里，dp[i] = max(dp[j1], dp[j2], ...)——两个候选来自同一个更小子问题时，取 max 不会重复计数。计数 DP 里，dp[i] = dp[j1] + dp[j2] + ...——如果 j1 和 j2 对应的方案集合有重叠，同一个方案会被数两次。

所以计数 DP 的铁律：分类必须不重不漏。 每个转移分支对应一组方案，这些组两两无交，且并起来恰好是全部方案。加法原理的「互斥」前提，就是「不重不漏」。

转移中的加法原理与乘法原理

• 加法原理（同一个状态的多条入边）： 把方案按「最后一步怎么走」分类，各类方案数相加 → 转移求和；
• 乘法原理（一条路径上的独立选择）： 方案数 = 各阶段选择数的乘积 → DP 里通常体现为「初始化 dp[0] = 1」（空方案，一个什么都不选的方案）以及「组合数 = 两个独立 DP 结果相乘」的合并。

完整实战一：数字组合（01 背包型计数）

回到开篇的题 2。这其实就是 6.2 章 0/1 背包的计数版：物品是 1..N，每件「重量」等于面值，每个容积恰好装满的方案数。

状态： f[j] = 从已考虑的数中选若干个、和恰好为 j 的方案数。

转移（逐个数 x = 1..N 考虑，0/1 背包倒序）：

$$f[j] \mathrel{+}= f[j - x] \quad (\text{对每个 } x,\ j \text{ 从 } K \text{ 倒序到 } x)$$

为什么倒序？正序时 f[j-x] 可能已经包含「选了 x」的方案，同一个方案（x 被选两次）会被重复计数——这正是 6.1 章背包容量的老朋友。计数 DP 里背包循环方向错误的表现不是 WA 在最优值，而是方案数凭空变多。

初始化： f[0] = 1（空集，和为 0，恰好一个方案）。这是计数 DP 最重要的初始化，忘了它全部输出 0。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    long long MOD;
    cin >> n >> k >> MOD;
    vector<long long> f(k + 1, 0);
    f[0] = 1;                              // 空方案
    for (int x = 1; x <= n; x++)
        for (int j = k; j >= x; j--)       // 0/1 背包：倒序防重复
            f[j] = (f[j] + f[j - x]) % MOD;
    cout << f[k] << "\n";
    return 0;
}

手算核对：

输入：4 4 1000000007
输出：2

从 {1,2,3,4} 中选数凑和为 4：{4} 和 {1,3}——共 2 种。✓

输入：4 6 1000000007
输出：2

凑和为 6：{2,4} 和 {1,2,3}——共 2 种。✓

复杂度： O(N·K)。

完整实战二：错排（上楼梯变体）

题目： 有 n 个人排队领 n 份不同的礼物，每人领一份。要求没有人拿到自己的那一份（第 i 人不拿礼物 i）。求方案数，对 MOD 取模。n ≤ 10⁶。

「错排」是计数 DP 的经典模型——它不能像背包那样直接「最后一步分类」，因为约束（每人不拿自己的）把方案互相缠在一起。推导如下：

考虑第 1 个人（拿礼物 1 的人）。他必须拿别人的礼物，设他拿了礼物 i（i ≠ 1，有 n-1 种）。现在看礼物 1 归谁，按两种情况分类——这个分类不重不漏：

• 情况 A：第 i 个人拿礼物 1。 1 和 i 互换，剩下 n-2 个人和 n-2 份礼物构成同样的错排问题：D(n-2) 种；
• 情况 B：第 i 个人不拿礼物 1。 把「第 i 个人不能拿礼物 1」看成「礼物 1 是他的『自己的礼物』」，剩下 n-1 个人构成错排：D(n-1) 种。

$$D_n = (n-1),\bigl(D_{n-1} + D_{n-2}\bigr), \qquad D_0 = 1,\ D_1 = 0$$

这个推导值得反复回味：先固定一个「关键人物」的选择做乘法，再按剩余局面的形态做不重不漏的分类——这是很多计数题的标准套路。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long MOD;
    cin >> n >> MOD;
    vector<long long> f(n + 1);
    f[0] = 1; f[1] = 0;
    for (int i = 2; i <= n; i++)
        f[i] = ((long long)(i - 1) * ((f[i-1] + f[i-2]) % MOD)) % MOD;
    cout << f[n] << "\n";
    return 0;
}

手算核对：

输入：3 1000000007
输出：2

3 个人的错排：2 3 1 和 3 1 2——共 2 种。✓（D_3 = 2·(D_2+D_1) = 2·(1+0) = 2）

输入：4 1000000
输出：9

D_4 = 3·(D_3+D_2) = 3·(2+1) = 9。✓（顺带展示了取模：9 < 10⁶ 没影响，但大规模数据必须每步取模。）

复杂度： O(N)。

不重不漏怎么检查？

写完转移后，问自己三个问题：

1. 每个方案走到哪个分支？（漏：某方案不属于任何分支）
2. 一个方案会不会走两个分支？（重：分支之间有交）
3. 分支里的子问题是否和原问题同型？（不等型的「子问题」会让答案错得很安静）

最实用的手段：写一个 O(2ⁿ) 的暴力枚举程序，小数据对拍。计数题的 bug 几乎总是「重」——输出比暴力大——对拍一跑就现形。

6.7.4 完整实战：换教室（简化版，NOIP2016 风格）

现在把期望 DP 用在一道带决策的题上——期望与最优化的混合体，NOIP2016 换教室的简化版：

题目： 牛牛要上 n 个时间段的课。第 i 节课在教室 c[i]，牛牛可以申请换到教室 d[i]，申请成功的概率是 p[i]；他最多能申请 m 节课。上完第 i 节课要走到第 i+1 节课的教室（第 1 节课之前不用移动）。教室共 v 间，走廊长度已知（无向图）。合理选择申请哪几节课，使移动总路程的期望最小。n, m ≤ 2000，v ≤ 300，边长 ≤ 100， Floyd 后转移 O(1)。

第一步：预处理。 牛牛每一步从「上一节课的两个可能教室之一」走到「这一节课的两个可能教室之一」，需要任意两点间最短路。v ≤ 300——直接 Floyd，O(v³) = 2.7×10⁷。

第二步：状态。 移动是一节一节发生的，每节的起点/终点各有两种可能，概率由「是否申请」决定。定义

f[i][j][0/1] = 上完前 i 节课、其中申请了 j 节、
               第 i 节课没申请(0)/申请了(1) 时，已花费的期望路程

注意两个细节：

• 申请了 ≠ 成功——第 i 节申请后教室是 d[i] 的概率 p[i]、是 c[i] 的概率 1-p[i]，期望路程要按概率加权；
• 答案是 min over j ≤ m of min(f[n][j][0], f[n][j][1])——申请次数是预算，不多于 m。

第三步：转移（核心：把「上一节的随机教室」和「这一节的随机教室」两个不确定性都展开）。

从第 i-1 节走到第 i 节，起点有 {c[i-1], d[i-1]} 两种（若上一节申请了），终点有 {c[i], d[i]} 两种（若这一节申请了）。四种组合，每种组合的概率 = 两个边缘概率相乘（申请是否成功互相独立），期望路程 = Σ 概率 × 最短路长。

以「第 i-1 节申请、第 i 节不申请」为例：

$$f_{i,j,0} \leftarrow f_{i-1,j,1} + p_{i-1}, w_{d_{i-1},,c_i} + (1-p_{i-1}), w_{c_{i-1},,c_i}$$

「两节都申请」的分支要展开成四项：

$$f_{i-1,j-1,1} + p_{i-1}p_i, w_{d_{i-1},d_i} + p_{i-1}(1-p_i), w_{d_{i-1},c_i} + (1-p_{i-1})p_i, w_{c_{i-1},d_i} + (1-p_{i-1})(1-p_i), w_{c_{i-1},c_i}$$

每个 f[i][j][*] 取所有合法前驱的最小值。初始化： f[1][0][0] = f[1][1][1] = 0（第 1 节课前没有移动），其余为 +∞。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, v;
    cin >> n >> m >> v;
    vector<int> c(n + 1), d(n + 1);
    vector<double> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> c[i] >> d[i] >> p[i];
    const double INF = 1e18;
    vector<vector<double>> w(v + 1, vector<double>(v + 1, INF));
    for (int i = 1; i <= v; i++) w[i][i] = 0;
    int e;
    cin >> e;
    for (int i = 0; i < e; i++) {
        int a, b, len;
        cin >> a >> b >> len;
        w[a][b] = w[b][a] = min(w[a][b], (double)len);
    }
    for (int k = 1; k <= v; k++)                      // Floyd
        for (int i = 1; i <= v; i++)
            for (int j = 1; j <= v; j++)
                if (w[i][k] + w[k][j] < w[i][j]) w[i][j] = w[i][k] + w[k][j];

    vector<vector<array<double,2>>> f(
        n + 1, vector<array<double,2>>(m + 1, {INF, INF}));
    f[1][0][0] = 0.0;
    f[1][1][1] = 0.0;                                  // 第 1 节申请也行
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= min(m, i); j++) {
            // 第 i 节不申请
            double best0 = INF;
            if (f[i-1][j][0] < INF)
                best0 = min(best0, f[i-1][j][0] + w[c[i-1]][c[i]]);
            if (f[i-1][j][1] < INF)
                best0 = min(best0, f[i-1][j][1]
                    + p[i-1] * w[d[i-1]][c[i]]
                    + (1 - p[i-1]) * w[c[i-1]][c[i]]);
            f[i][j][0] = best0;
            // 第 i 节申请
            if (j >= 1) {
                double best1 = INF;
                if (f[i-1][j-1][0] < INF)
                    best1 = min(best1, f[i-1][j-1][0]
                        + p[i] * w[c[i-1]][d[i]]
                        + (1 - p[i]) * w[c[i-1]][c[i]]);
                if (f[i-1][j-1][1] < INF)
                    best1 = min(best1, f[i-1][j-1][1]
                        + p[i-1] * p[i] * w[d[i-1]][d[i]]
                        + p[i-1] * (1 - p[i]) * w[d[i-1]][c[i]]
                        + (1 - p[i-1]) * p[i] * w[c[i-1]][d[i]]
                        + (1 - p[i-1]) * (1 - p[i]) * w[c[i-1]][c[i]]);
                f[i][j][1] = best1;
            }
        }
    }
    double ans = INF;
    for (int j = 0; j <= m; j++)
        ans = min(ans, min(f[n][j][0], f[n][j][1]));
    cout << fixed << setprecision(2) << ans << "\n";
    return 0;
}

手算核对（三个小样例）：

输入：
2 1 2
1 2 1.0
2 1 1.0
1
1 2 10

输出：0.00

两节课、可申请 1 节。第 1 节申请（p=1，必成功）→ 在教室 2；第 2 节申请（p=1）→ 在教室 1。从教室 2 走到教室 1 距离 10？不对——仔细看：申请第 1 节（到 2）和第 2 节（到 1），路程 w[2][1] = 10；但如果都不申请：教室 1 → 教室 2，也是 10；申请第 1 节、不申请第 2 节：2 → 2，路程 0！所以最优是期望 0。✓ 程序输出 0.00。

输入：
3 1 3
1 1 0.0
2 3 0.5
3 1 1.0
3
1 2 1
2 3 1
1 3 10

输出：2.00

教室 1–2 距离 1，2–3 距离 1，1–3 距离 10。三节课固定教室序列 1, 2, 3：不申请时路程 1 + 1 = 2。唯一的申请机会用在第 2 节（p=0.5 换到 3）：w[2][3] + 0.5·w[3][3] + 0.5·w[3][3] = 1 + 0，第 1→2 段仍是 1，总期望还是 2；用在别处更差（比如第 3 节换到 1：1 + 0.5·w[2][1] + 0.5·w[2][3] = 1 + 0.5 + 0.5 = 2）。最优 2.00。✓

输入：
3 1 3
1 1 0.0
2 3 0.5
3 1 1.0
3
1 2 1
2 3 1
1 3 1.5

输出：1.50

这个样例把「申请第 2 节」的价值展示得最充分。教室 1–2 距离 1，2–3 距离 1，1–3 距离 1（这条「抄近道」的边是本题的关键）。三节课的固定教室序列仍是 1, 2, 3。逐个方案算期望：

• 都不申请：w[1][2] + w[2][3] = 1 + 1 = 2；
• 申请第 3 节（p=1，必到教室 1）：第 2→3 段变成 w[2][1] = 1，总 1 + 1 = 2；
• 申请第 2 节（p=0.5，教室随机为 3 或 2）：
  • 第 1→2 段：起点确定是教室 1，终点随机（3 或 2，各 0.5）：0.5·w[1][3] + 0.5·w[1][2] = 0.5×1 + 0.5×1 = 1；
  • 第 2→3 段：起点随机（3 或 2，各 0.5），终点确定是教室 3：0.5·w[3][3] + 0.5·w[2][3] = 0 + 0.5 = 0.5；
  • 总期望 1 + 0.5 = 1.5。✓

注意一个容易犯的手算错误： 算第 1→2 段的期望时，只有「这一段涉及的那节课」的申请才有随机性——第 2 节申请影响的是第 1→2 段的终点和第 2→3 段的起点，两段各算各的，然后按期望线性性相加（两段路程显然不独立，但线性性不要求独立）。若把第 1→2 段的终点错误地当成确定值、或把随机性算串了段，就会得到错误的期望。用 w[1][3] = 1.5 的图（其他条件相同）重算本例答案是 1.75（第 1→2 段期望变成 1.25）——你可以在纸上推一遍，体会边长对期望的影响。

复杂度： Floyd O(v³) + DP O(n·m) 转移 O(1)。

这道题的通用模式： 「期望 + 最优决策」的题，状态里除了描述随机性的维度，还要加「预算/已用决策」维度（本题的 j），转移时对每个决策取 min、对每个随机结果按概率加权求和。期望 DP 和普通 DP 在这里合流。

⚠️ 概率期望与计数 DP 常见错误

本章总结

📌 三类 DP 对照表

🧩 核心方程速查

// 概率 DP（顺推）
dp[初始] = 1.0;
dp[下一状态] += dp[当前] * p;

// 期望 DP（倒推）
f[终点] = 0;
f[i] = 1 + Σ p_j * f[j];        // 自环先移项解出 f[i]

// 计数 DP（0/1 背包型，倒序防重）
f[0] = 1;
for (每个物品 x)
    for (j = K; j >= x; j--)
        f[j] = (f[j] + f[j-x]) % MOD;

// 错排
D[0] = 1; D[1] = 0;
D[i] = (i-1) * (D[i-1] + D[i-2]) % MOD;

❓ 常见问题

Q1：期望 DP 什么时候不能倒推？

A：当状态之间有环且移项解不动时（如机器人网格上可左右移动，f[i][j] 依赖同行左右两格），需要高斯消元解方程组，复杂度 O(m³) 每行。NOIP/USACO Silver-Gold 层面掌握「无环倒推」即可，遇到有环先尝试移项。

Q2：为什么期望的题几乎总问「期望步数/花费」而不是「期望概率」？

A：因为「步数、花费」天然可加，能吃期望线性性的红利——每一步贡献独立可算。问「最终落在某个格子的概率」时，你要做的其实是概率 DP（顺推转移概率）。

Q3：计数 DP 的答案为什么经常大得离谱？

A：方案数随规模指数增长（错排 D(n) ≈ n!/e），n = 1000 时位数超过 long long。所以计数题几乎全部要求对某个 MOD 取模，且每一步运算后立即取模，不能只在最后取。

练习题

题目 6.7.1 — 概率 DP：袋中老鼠（Codeforces 148D Bag of mice） 🟡 中等 袋子里有 w 只白鼠和 b 只黑鼠。公主和龙轮流抓老鼠，公主先抓。谁先抓到白鼠谁赢；袋子空了且没出现白鼠则龙赢。公主每次抓一只；龙每次抓完一只后还会吓跑一只随机老鼠。求公主赢的概率。w, b ≤ 1000。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int w, b;
    cin >> w >> b;
    // f[i][j]：轮到公主、袋中 i 白 j 黑时公主的获胜概率
    vector<vector<double>> f(w + 1, vector<double>(b + 1, 0.0));
    for (int i = 1; i <= w; i++) f[i][0] = 1.0;   // 一抓就是白鼠
    for (int i = 1; i <= w; i++)
        for (int j = 1; j <= b; j++) {
            double p = 0.0;
            // 公主抓到白鼠：直接赢
            p += (double)i / (i + j);
            // 公主黑、龙黑、跑出黑鼠：递归到 (i, j-3)
            if (j >= 3)
                p += (double)j / (i + j) * (j - 1) / (i + j - 1)
                        * (j - 2) / (i + j - 2) * f[i][j-3];
            // 公主黑、龙黑、跑出白鼠：递归到 (i-1, j-2)
            if (j >= 2 && i >= 1)
                p += (double)j / (i + j) * (j - 1) / (i + j - 1)
                        * (double)i / (i + j - 2) * f[i-1][j-2];
            // 公主黑、龙白：公主输，不加项
            f[i][j] = p;
        }
    cout << fixed << setprecision(9) << f[w][b] << "\n";
    return 0;
}

手算核对： w=1, b=1：公主 1/2 直接赢；1/2 抓黑后龙只剩白鼠必赢 → 概率 0.5。w=1, b=2：公主 1/3 赢；公主黑（2/3）后龙必抓走白鼠或黑鼠——龙抓白（1/2）龙赢，龙抓黑（1/2）后跑出的必是白鼠，袋空龙赢——所以概率 1/3 ≈ 0.333。运行验证：输入 1 1 输出 0.500000000，输入 1 2 输出 0.333333333。✓

题目 6.7.2 — 期望 DP：收集邮票（简化版） 🟡 中等 有 n 种邮票，每次花 1 元随机（等概率）买到一张（可能重复）。求集齐所有 n 种的期望花费。n ≤ 1000。（原版 P4550 花费是递增的第 k 张花 k 元，这里简化为每张 1 元。）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<double> f(n + 1, 0.0);
    for (int i = n - 1; i >= 0; i--) {
        double pNew = (double)(n - i) / n;   // 买到新种类
        double pOld = (double)i / n;         // 买到已有的
        // f[i] = 1 + pOld*f[i] + pNew*f[i+1]，自环移项：
        f[i] = (1.0 + pNew * f[i + 1]) / (1.0 - pOld);
    }
    cout << fixed << setprecision(6) << f[0] << "\n";
    return 0;
}

手算核对： n=1：第一次必中，期望 1。n=2：f[1] = (1 + 0.5·0)/0.5 = 2，f[0] = (1 + 1·f[1])/1 = 3——先买到第一种（1 张），再等第二种（几何分布期望 2 张），共 3 张。✓（这也是自环移项的标准示范。）

题目 6.7.3 — 期望 DP + 手算训练：换教室填表（本章 6.7.4 第三个样例） 🟢 简单 对 6.7.4 的第三个样例，写出 f[i][j][0/1] 的完整填表过程（f[2][1][1] = 1.0、f[3][1][0] = 1.5 等），再修改一条边长（如把 1 3 1 改成 1 3 1.5）重新填表，验证答案是 1.75。输入格式见 6.7.4 代码。

💡 下一步： 概率期望 DP 是数论与概率论的交汇点，计数 DP 则是组合数学在程序里的化身。第七部分图论中你会在随机游走、最小斯坦纳树等话题里再次遇到「按概率加权」的转移；而计数 DP 的思想将在字符串部分的哈希与 SAM 统计中反复出现。把「不重不漏」四个字刻进肌肉记忆。