# 概率与期望 DP 学习讲义

## 1. 核心概念

期望（Expectation）是随机变量平均值的大小。在算法竞赛中，期望题目通常具有**线性性质**，且其状态转移方程的思想与动态规划（DP）非常相似，因此常被称为**期望 DP**。

### 1.1 期望的定义
若 $X$ 是一个离散型随机变量，其输出值为 $x\_1, x\_2, \dots, x\_n$，取得相应值的概率为 $p\_1, p\_2, \dots, p\_n$（且 $\sum p\_i = 1$），则期望值为：
$$E(X) = \sum\_{i=1}^n x\_i p\_i$$

*   **例子**：投一枚六面骰子，点数 $X$ 的期望为 $E(X) = 1 \cdot \frac{1}{6} + 2 \cdot \frac{1}{6} + \dots + 6 \cdot \frac{1}{6} = 3.5$。

### 1.2 期望的线性性质
对于任意随机变量 $X, Y$ 及常数 $a, b$：
$$E(aX + bY) = aE(X) + bE(Y)$$
**注意**：无论 $X$ 和 $Y$ 是否独立，该线性性质均成立。

---

## 2. 期望 DP 的常用策略
1.  **逆推法**：大多数期望 DP 采用逆推。设 $dp[i]$ 为“从当前状态 $i$ 到达终点状态的期望”。
    *   原因：终点状态（如 $dp[target]$）通常已知为 0，而起点状态是要求的答案。
2.  **消除自环（消元）**：如果状态转移方程中出现 $dp[i]$ 依赖于自身（例如有概率留在原状态），需通过代数移项将 $dp[i]$ 移到等号左边求解。

---

## 3. 经典例题与代码实现

### 3.1 例题一：数字变换（约数递推）
**题目**：给你一个整数 $n$，每次会变成 $n$ 的某个因子（含 $1$ 和 $n$），求变成 $1$ 的期望步数。

**分析**：
设 $dp[i]$ 表示变成 $1$ 的期望步数。假设 $i$ 有 $k$ 个约数 $d\_1, d\_2, \dots, d\_k$（其中包含 $i$ 本身）。
$$dp[i] = \frac{1}{k} \sum\_{j=1}^k dp[d\_j] + 1$$
由于 $d\_k = i$，移项得：
$dp[i] = \frac{\sum\_{j=1}^{k-1} dp[d\_j] + k}{k-1}$

```cpp
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

const int MAXN = 100005;
double dp[MAXN];

void solve_example1(int n) {
    dp[1] = 0; // 终点
    for (int i = 2; i <= n; ++i) {
        vector<int> factors;
        for (int j = 1; j * j <= i; ++j) {
            if (i % j == 0) {
                factors.push_back(j);
                if (j * j != i) factors.push_back(i / j);
            }
        }
        int k = factors.size();
        double sum_dp = 0;
        for (int f : factors) {
            if (f != i) sum_dp += dp[f];
        }
        dp[i] = (sum_dp + k) / (k - 1); // 移项后的公式
    }
    printf("%.4f\n", dp[n]);
}
```

---

### 3.2 例题二：找 Bug（POJ 2096）
**题目**：$n$ 种 Bug，$s$ 个子系统。每天发现一个 Bug，属于某种分类的概率是 $1/n$，属于某个系统的概率是 $1/s$。求集齐 $n$ 种 Bug 且每个系统都至少有一个 Bug 的期望天数。

**状态定义**：`dp[i][j]` 表示已经找到 $i$ 种分类、$j$ 个系统的 Bug，距离目标状态的期望天数。

```cpp
#include <iostream>
#include <cstdio>

using namespace std;

double dp[1005][1005];

void solve_bug(int n, int s) {
    dp[n][s] = 0.0; // 目标状态
    for (int i = n; i >= 0; --i) {
        for (int j = s; j >= 0; --j) {
            if (i == n && j == s) continue;
            
            // 四种转移情况
            double p1 = (double)i * j / (n * s);           // 留在原地
            double p2 = (double)i * (s - j) / (n * s);     // 增加一个系统
            double p3 = (double)(n - i) * j / (n * s);     // 增加一个分类
            double p4 = (double)(n - i) * (s - j) / (n * s); // 均增加
            
            // dp[i][j] = p1*dp[i][j] + p2*dp[i][j+1] + p3*dp[i+1][j] + p4*dp[i+1][j+1] + 1
            // 移项消去左侧 dp[i][j]:
            dp[i][j] = (p2 * dp[i][j + 1] + p3 * dp[i + 1][j] + p4 * dp[i + 1][j + 1] + 1) / (1 - p1);
        }
    }
    printf("%.4f\n", dp[0][0]);
}
```

---

### 3.3 例题三：收集邮票（赠券收集者问题）
**题目**：有 $n$ 种不同的邮票，每次随机抽取一张，求收集齐所有种类所需的期望次数。

**分析**：
设 $dp[i]$ 表示已收集 $i$ 种，还需收集齐剩下 $n-i$ 种的期望次数。
$dp[i] = \frac{i}{n} dp[i] + \frac{n-i}{n} dp[i+1] + 1$
化简得：$dp[i] = dp[i+1] + \frac{n}{n-i}$

```cpp
double solve_stamps(int n) {
    double res = 0;
    for (int i = 1; i <= n; ++i) {
        res += (double)n / i; // 即 n/n + n/(n-1) + ... + n/1
    }
    return res;
}
```

---

### 3.4 例题四：扔骰子（后缀和优化）
**题目**：掷 $n$ 面骰子。若掷出的点数比历史最高大，则得分增加该点数；若 $\le$ 历史最高，游戏结束。求总分期望。

**分析**：
设 $dp[i]$ 表示当前最高点数为 $i$ 时，直到游戏结束能获得的额外期望得分。
$dp[i] = \sum\_{x=i+1}^n \frac{1}{n} (x + dp[x])$
由于 $dp[i]$ 取决于比它大的值，使用后缀和优化到 $O(n)$。

```cpp
#include <vector>
#include <iomanip>

double solve_dice(int n) {
    vector<double> dp(n + 1, 0.0);
    double suffix_sum = 0.0; // 维护 (x + dp[x]) 的和
    
    for (int i = n; i >= 1; --i) {
        if (i == n) dp[i] = 0;
        else dp[i] = suffix_sum / n;
        
        suffix_sum += (i + dp[i]);
    }
    return suffix_sum / n; // 第一次投掷的期望结果
}
```

---

## 4. 总结与考试建议

1.  **分清顺推与逆推**：如果终点已知，通常逆推；如果需要计算到达每个状态的概率，则顺推。
2.  **公式推导**：先写出包含自环的原始方程，然后再手动移项化简，不要在代码里处理复杂的代数式。
3.  **精度与边界**：
    *   使用 `double` 保证精度。
    *   循环边界要防止数组越界（如 `i+1 <= n`）。
    *   **分母为零**：移项后的分母如果可能为 0（通常是目标状态），务必特判跳过。

概率与期望 DP 学习讲义

1. 核心概念

期望（Expectation）是随机变量平均值的大小。在算法竞赛中，期望题目通常具有线性性质，且其状态转移方程的思想与动态规划（DP）非常相似，因此常被称为期望 DP。

1.1 期望的定义

若 $X$ 是一个离散型随机变量，其输出值为 $x_1, x_2, \dots, x_n$，取得相应值的概率为 $p_1, p_2, \dots, p_n$（且 $\sum p_i = 1$），则期望值为： $$E(X) = \sum_{i=1}^n x_i p_i$$

例子：投一枚六面骰子，点数 $X$ 的期望为 $E(X) = 1 \cdot \frac{1}{6} + 2 \cdot \frac{1}{6} + \dots + 6 \cdot \frac{1}{6} = 3.5$。

1.2 期望的线性性质

对于任意随机变量 $X, Y$ 及常数 $a, b$： $$E(aX + bY) = aE(X) + bE(Y)$$ 注意：无论 $X$ 和 $Y$ 是否独立，该线性性质均成立。

2. 期望 DP 的常用策略

逆推法：大多数期望 DP 采用逆推。设 $dp[i]$ 为“从当前状态 $i$ 到达终点状态的期望”。
- 原因：终点状态（如 $dp[target]$）通常已知为 0，而起点状态是要求的答案。
消除自环（消元）：如果状态转移方程中出现 $dp[i]$ 依赖于自身（例如有概率留在原状态），需通过代数移项将 $dp[i]$ 移到等号左边求解。

3. 经典例题与代码实现

3.1 例题一：数字变换（约数递推）

题目：给你一个整数 $n$，每次会变成 $n$ 的某个因子（含 $1$ 和 $n$），求变成 $1$ 的期望步数。

分析：设 $dp[i]$ 表示变成 $1$ 的期望步数。假设 $i$ 有 $k$ 个约数 $d_1, d_2, \dots, d_k$（其中包含 $i$ 本身）。 $$dp[i] = \frac{1}{k} \sum_{j=1}^k dp[d_j] + 1$$ 由于 $d_k = i$，移项得： $dp[i] = \frac{\sum_{j=1}^{k-1} dp[d_j] + k}{k-1}$

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

const int MAXN = 100005;
double dp[MAXN];

void solve_example1(int n) {
    dp[1] = 0; // 终点
    for (int i = 2; i <= n; ++i) {
        vector<int> factors;
        for (int j = 1; j * j <= i; ++j) {
            if (i % j == 0) {
                factors.push_back(j);
                if (j * j != i) factors.push_back(i / j);
            }
        }
        int k = factors.size();
        double sum_dp = 0;
        for (int f : factors) {
            if (f != i) sum_dp += dp[f];
        }
        dp[i] = (sum_dp + k) / (k - 1); // 移项后的公式
    }
    printf("%.4f\n", dp[n]);
}

3.2 例题二：找 Bug（POJ 2096）

题目：$n$ 种 Bug，$s$ 个子系统。每天发现一个 Bug，属于某种分类的概率是 $1/n$，属于某个系统的概率是 $1/s$。求集齐 $n$ 种 Bug 且每个系统都至少有一个 Bug 的期望天数。

状态定义：dp[i][j] 表示已经找到 $i$ 种分类、$j$ 个系统的 Bug，距离目标状态的期望天数。

#include <iostream>
#include <cstdio>

using namespace std;

double dp[1005][1005];

void solve_bug(int n, int s) {
    dp[n][s] = 0.0; // 目标状态
    for (int i = n; i >= 0; --i) {
        for (int j = s; j >= 0; --j) {
            if (i == n && j == s) continue;

            // 四种转移情况
            double p1 = (double)i * j / (n * s);           // 留在原地
            double p2 = (double)i * (s - j) / (n * s);     // 增加一个系统
            double p3 = (double)(n - i) * j / (n * s);     // 增加一个分类
            double p4 = (double)(n - i) * (s - j) / (n * s); // 均增加

            // dp[i][j] = p1*dp[i][j] + p2*dp[i][j+1] + p3*dp[i+1][j] + p4*dp[i+1][j+1] + 1
            // 移项消去左侧 dp[i][j]:
            dp[i][j] = (p2 * dp[i][j + 1] + p3 * dp[i + 1][j] + p4 * dp[i + 1][j + 1] + 1) / (1 - p1);
        }
    }
    printf("%.4f\n", dp[0][0]);
}

3.3 例题三：收集邮票（赠券收集者问题）

题目：有 $n$ 种不同的邮票，每次随机抽取一张，求收集齐所有种类所需的期望次数。

分析：设 $dp[i]$ 表示已收集 $i$ 种，还需收集齐剩下 $n-i$ 种的期望次数。 $dp[i] = \frac{i}{n} dp[i] + \frac{n-i}{n} dp[i+1] + 1$ 化简得：$dp[i] = dp[i+1] + \frac{n}{n-i}$

double solve_stamps(int n) {
    double res = 0;
    for (int i = 1; i <= n; ++i) {
        res += (double)n / i; // 即 n/n + n/(n-1) + ... + n/1
    }
    return res;
}

3.4 例题四：扔骰子（后缀和优化）

题目：掷 $n$ 面骰子。若掷出的点数比历史最高大，则得分增加该点数；若 $\le$ 历史最高，游戏结束。求总分期望。

分析：设 $dp[i]$ 表示当前最高点数为 $i$ 时，直到游戏结束能获得的额外期望得分。 $dp[i] = \sum_{x=i+1}^n \frac{1}{n} (x + dp[x])$ 由于 $dp[i]$ 取决于比它大的值，使用后缀和优化到 $O(n)$。

#include <vector>
#include <iomanip>

double solve_dice(int n) {
    vector<double> dp(n + 1, 0.0);
    double suffix_sum = 0.0; // 维护 (x + dp[x]) 的和

    for (int i = n; i >= 1; --i) {
        if (i == n) dp[i] = 0;
        else dp[i] = suffix_sum / n;

        suffix_sum += (i + dp[i]);
    }
    return suffix_sum / n; // 第一次投掷的期望结果
}

4. 总结与考试建议

分清顺推与逆推：如果终点已知，通常逆推；如果需要计算到达每个状态的概率，则顺推。
公式推导：先写出包含自环的原始方程，然后再手动移项化简，不要在代码里处理复杂的代数式。
精度与边界：
- 使用 double 保证精度。
- 循环边界要防止数组越界（如 i+1 <= n）。
- 分母为零：移项后的分母如果可能为 0（通常是目标状态），务必特判跳过。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

概率 DP 与数学期望