Skip to main content

概率 DP

参考资料​

简介​

概率 DP 将概率或期望值作为 DP 状态，通过全概率公式或期望的线性性建立转移方程。求概率通常正向递推（从初始状态推向目标），求期望通常逆向递推（从目标状态推向初始）。若方程存在后效性（状态依赖自身），需联立方程组或高斯消元求解。

以「收集全部 nn 种漏洞分类和 ss 个子系统漏洞的期望天数」为例：设 fi,jf_{i,j} 为已发现 ii 种分类和 jj 个子系统时距离完成的期望天数，fn,s=0f_{n,s}=0。每天随机发现一个漏洞，四种情况按概率加权转移：

fi,j=p2⋅fi,j+1+p3⋅fi+1,j+p4⋅fi+1,j+1+11−p1f_{i,j}=\frac{p_2\cdot f_{i,j+1}+p_3\cdot f_{i+1,j}+p_4\cdot f_{i+1,j+1}+1}{1-p_1}

其中 p1=in⋅jsp_1=\frac{i}{n}\cdot\frac{j}{s}（重复），p2=in⋅(1−js)p_2=\frac{i}{n}\cdot\left(1-\frac{j}{s}\right)，p3=(1−in)⋅jsp_3=\left(1-\frac{i}{n}\right)\cdot\frac{j}{s}，p4=(1−in)⋅(1−js)p_4=\left(1-\frac{i}{n}\right)\cdot\left(1-\frac{j}{s}\right)。从 (n,s)(n,s) 逆推至 (0,0)(0,0)，答案为 f0,0f_{0,0}，时间复杂度 O(ns)O(ns)。

实现​

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

const int N=1005;
double f[N][N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,s;
	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;
			double p1=(double)i/n*(double)j/s;
			double p2=(double)i/n*(1.0-1.0*j/s);
			double p3=(1.0-1.0*i/n)*(double)j/s;
			double p4=(1.0-1.0*i/n)*(1.0-1.0*j/s);
			f[i][j]=(p2*f[i][j+1]+p3*f[i+1][j]+p4*f[i+1][j+1]+1)/(1-p1);
		}
	}
	cout<<fixed<<setprecision(4)<<f[0][0]<<'\n';
	return 0;
}

例题​

洛谷 P2719 搞笑世界杯

共 2n2n 张球票，其中 nn 张 A 票、nn 张 B 票，2n2n 个人排队每人取一张。求排在队尾的两人取到同一种票（都为 A 或都为 B）的概率。