概率DP和期望DP

概率DP&期望DP

入门而已啦QAQ

两者好像是属于同一类问题（？

但思路总体恰恰相反：

概率DP:

采用顺推，也就是从初始状态推向结果。

期望DP:

采用逆推，从末状态推向结果。

（可能有点抽象

看几道经典例题吧！

概率DP

1. Bag of mice

思路：

我们分类讨论所有情况，

设 $f[i][j]$为轮到公主时袋子里有$i$ 只白鼠，$j$ 只黑鼠，公主赢的概率。

初始化边界， $f[0][i]=0$因为没有白鼠了算龙赢， $f[i][0]=1$因为抓一只就是白鼠，公主赢。 考虑$f[i][j]$ 的转移：

• 公主抓到一只白鼠，公主赢了。概率为 $\frac{i}{i+j}$；
• 公主抓到一只黑鼠，龙抓到一只白鼠，龙赢了。概率为$\frac{j}{i+j}\times \frac{i}{i+j-1}$；
• 公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只黑鼠，转移到 $f[i][j-3]$。概率为$\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{j-2}{i+j-2}$ ；
• 公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只白鼠，转移到 $f[i-1][j-2]$。概率为$\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{i-1}{i+j-2}$ ；

一定只有这四种情况！

考虑公主赢的概率，第二种情况不参与计算。并且要保证后两种情况合法，所以还要判断$i,j$ 的大小，满足第三种情况至少要有 $3$ 只黑鼠，满足第四种情况要有 $1$ 只白鼠和 $2$ 只黑鼠。

然后是简简单单的代码

#include 
#define endl '\n'
#define int long long

using namespace std;

const int N = 1010;

double f[N][N];//轮到公主，有i个白鼠j个黑鼠，公主赢的概率
int a, b;

void solve()
{
    cin >> a >> b;
    for (int i = 0; i <= a; i++) f[i][0] = 1;
    for (int i = 0; i <= b; i++) f[0][i] = 0;
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
        {
            f[i][j] += 1.0 * i / (i + j);
            if (j > 2) f[i][j] += 1.0 * j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * f[i][j - 3];
            if (i > 0 && j > 1) f[i][j] += 1.0 * j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * f[i - 1][j - 2];
        }
    printf("%.9f", f[a][b]);
}
signed main(){
    // ios_base::sync_with_stdio(false), cin.tie(0);
    int T = 1;// cin >> T;
    while(T--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2. Jon and Orbs

转移方程好好推捏，但代码实现（对憨憨）很不友好！

还是分类讨论：

令$f[i][j]$第$i$天产生了$j$种球的概率，他能转移到两种情况：第$j+1$天产生的是和以前相同种类的球，概率是$\frac{i}{k}$，转移到状态$f[i][j+1]$和第$j+1$天产生了一种新的类型的球，概率为$\frac{k-i}{k}$，转移到状态$f[i+1][j+1]$.

那么我们可以得到转移方程为：

f[i][j] = j / k * f[i][j + 1] + (k - j) / k * f[i + 1][j + 1]
1

但这是逆推，末状态我们是不知道的，我们只能知道初状态

f[0][0] = 1 && f[i][0] = 0(i != 0)
1

所以我们将思维逆转一下：

令$f[i][j]$第$i$天产生了$j$种球的概率，他能从两种情况转移而来：第$j$天产生的是和以前相同种类的球，概率是$\frac{i}{k}$，从状态$f[i][j-1]$转移过来和第$j$天产生了一种新的类型的球，概率为$\frac{k-(i-1)}{k}$，从状态$f[i-1][j-1]$转移过来.

那么我们可以得到转移方程为：

f[i][j] = j / k * f[i - 1][j] + (k - j + 1) / k * f[i - 1][j - 1]
//我们可以发现，下一维的i用的是上一维的i的数据，那么我们可以借助滚动数组采取逆序枚举来实现对第一维的优化
//注意f[i][0] = (i == 0 ? 0 : 1);
1
2
3

根据已知的初状态我们就可以求解了

#include 
#define endl '\n'
// #define int long long
 
using namespace std;
 
const int N = 1010;
 
// double f[N][N];
double f[N];//第一维用滚动数组实现
int day[N];
 
void solve()
{
    int k, q;
    cin >> k >> q;
    // f[0][0] =1;
    f[0] = 1;//当i==0时，f[i][0] = 1, 否则f[i][0] = 0
    int p = 1;
    for (int i = 1; p <= 1000; i++)
    {
        for (int j = k; j >= 1; j--)
        {
            // f[j] = (j * f[j] + (k - j + 1) * f[j - 1]) / k; //√
            f[j] = 1.0 * j / k * f[j] + 1.0 * (k - j + 1) / k * f[j - 1];//注意i,j都是整数，运算得不到想要的浮点数，所以别忘了精度转换！！！！！！！
        }
        while (f[k] * 2000 >= p + 1e-7) day[p] = i, p++;//只要第i天后的概率满足该pi，就一直记录答案直到不满足，继续循环下一天
        f[0] = 0;//之后用到的都是i>0的一层的结果，所以要改成0
    }    
    while(q--)//因为有多次询问，我们将所有的pi对应哪一天都预处理出来存在数组中
    {
        int x; cin >> x;
        printf("%d\n", day[x]);
    }
}
signed main(){
    // ios_base::sync_with_stdio(false), cin.tie(0);
    int T = 1;// cin >> T;
    while(T--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

期望DP

1. Collecting Bugs

令$f[i][j]$ 为已经找到$i$ 种 bug 分类，$j$ 个子系统的 bug，达到目标状态的期望天数。这里的目标状态是找到$n$ 种 bug 分类，$s$ 个子系统的 bug。那么就有$f[n][s]=0$ ，因为已经达到了目标状态，不需要用更多的天数去发现 bug 了，于是就以目标状态为起点开始递推，答案是$f[0][0]$。

考虑 的状态转移：

• $f[i][j]$发现一个 bug 属于已经发现的$i$ 种 bug 分类，$j$ 个子系统，概率为$p_1=\frac{i}{n}\times \frac{j}{s}$
• $f[i][j+1]$，发现一个 bug 属于已经发现的$i$ 种 bug 分类，不属于已经发现的子系统，概率为 $p_1=\frac{i}{n}\times \frac{s-j}{s}$
• $f[i+1][j]$，发现一个 bug 不属于已经发现 bug 分类，属于$j$ 个子系统，概率为 $p_1=\frac{n-i}{n}\times \frac{j}{s}$
• $f[i+1][j+1]$，发现一个 bug 不属于已经发现 bug 分类，不属于已经发现的子系统，概率为 $p_1=\frac{n-i}{n}\times \frac{s-j}{s}$

再根据期望的线性性质，就可以得到状态转移方程：

f[i][j] = p1 * f[i][j] + p2 * f[i][j + 1] + p3 * f[i + 1][j] + p4 * f[i + 1][j + 1]
//一定要化简后才能用来转移，因为我们要得到f[i][j]状态，只有等式左边才能有f[i][j],右边不能有！！！
//化简后
f[i][j] = ((j - s) * (i - n) * f[i + 1][j + 1] + j * (n - 2) * f[i + 1][j] + i * (s - j) * f[i][j + 1] + n * s) / (n * s - i * j)
1
2
3
4

简单的代码：

// #include 
#include 
#define endl '\n'
// #define int long long

using namespace std;

const int N = 1010;

int n, s;
double f[N][N];

void solve()
{
    cin >> n >> s;
    f[n][s] = 0;
    for (int i = n; i >= 0; i--)
        for (int j = s; j >= 0; j--)
        {
            if (i == n && j == s) continue;
            // f[i][j] =  f[i][j] * i / n * j / s  
            // + f[i + 1][j] * (n - i) / n * j / s 
            // + f[i][j + 1] * i / n * (s - j) / s  
            // + f[i + 1][j + 1] * (n - i) / n * (s - j) / s  
            // + 1;
            //未化简，不能用来状态转移哦
            f[i][j] = (f[i + 1][j + 1] * (j - s) * (i - n) + f[i + 1][j] * j * (n - i) + f[i][j + 1] * i * (s - j) + n * s) / (n * s - i * j);
        }
    printf("%.4f", f[0][0]);
}
signed main(){
    // ios_base::sync_with_stdio(false), cin.tie(0);
    int T = 1;// cin >> T;
    while(T--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

未完待续（希望如此。。。