概率DP&期望DP

入门而已啦QAQ

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

但思路总体恰恰相反：

概率DP:

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

期望DP:

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

（可能有点抽象

看几道经典例题吧！

概率DP

1. Bag of mice

思路：

我们分类讨论所有情况，

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

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

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

一定只有这四种情况！

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

然后是简简单单的代码

#include 
#define endl '\n'
#define int long longusing 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;
}

2. Jon and Orbs

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

还是分类讨论：

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

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

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

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

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

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

令f[i][j]f[i][j]f[i][j]第iii天产生了jjj种球的概率，他能从两种情况转移而来：第jjj天产生的是和以前相同种类的球，概率是ik\frac{i}{k}ki​，从状态f[i][j−1]f[i][j-1]f[i][j−1]转移过来和第jjj天产生了一种新的类型的球，概率为k−(i−1)k\frac{k-(i-1)}{k}kk−(i−1)​，从状态f[i−1][j−1]f[i-1][j-1]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);

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

#include 
#define endl '\n'
// #define int long longusing 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] = 0int 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;
}

期望DP

1. Collecting Bugs

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

考虑 的状态转移：

• f[i][j]f[i][j]f[i][j]发现一个 bug 属于已经发现的iii 种 bug 分类，jjj 个子系统，概率为p1=in×jsp_1=\frac{i}{n}\times \frac{j}{s}p1​=ni​×sj​
• f[i][j+1]f[i][j+1]f[i][j+1]，发现一个 bug 属于已经发现的iii 种 bug 分类，不属于已经发现的子系统，概率为 p1=in×s−jsp_1=\frac{i}{n}\times \frac{s-j}{s}p1​=ni​×ss−j​
• f[i+1][j]f[i+1][j]f[i+1][j]，发现一个 bug 不属于已经发现 bug 分类，属于jjj 个子系统，概率为 p1=n−in×jsp_1=\frac{n-i}{n}\times \frac{j}{s}p1​=nn−i​×sj​
• f[i+1][j+1]f[i+1][j+1]f[i+1][j+1]，发现一个 bug 不属于已经发现 bug 分类，不属于已经发现的子系统，概率为 p1=n−in×s−jsp_1=\frac{n-i}{n}\times \frac{s-j}{s}p1​=nn−i​×ss−j​

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

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)

简单的代码：

// #include 
#include 
#define endl '\n'
// #define int long longusing 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;
}

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