当前位置：首页 > news >正文

概率dp总结

news 来源：原创 2025/7/5 12:13:16

概率 DP 用于解决概率问题与期望问题，建议先对概率 & 期望的内容有一定了解。一般情况下，解决概率问题需要顺序循环，而解决期望问题使用逆序循环，如果定义的状态转移方程存在后效性问题，还需要用到高斯消元来优化。概率 DP 也会结合其他知识进行考察，例如状态压缩，树上进行 DP 转移等。

我们这一次博客首先来讲dp去求概率的问题，这种问题一般都是顺序向后推的，主要还是dp的状态转移方程式一般还是比较难找到的

我们来通过几个例题来感受一下这种概率dp的题目

D. Bag of mice

思路：我们每一次抽都会产生4种情况，

1.公主抽到白鼠游戏直接结束，公主获胜

~~2.公主抽到黑鼠，巨龙抽到白鼠，巨龙获胜~~

3.公主抽到黑鼠，巨龙抽到黑鼠，跑了一只白鼠，需要考虑剩下老鼠的情况

4.公主抽到黑鼠，巨龙抽到黑鼠，跑了一只黑鼠，需要考虑剩下老鼠的情况

因为我们考虑的是公主获胜的概率，因此可以直接将第二种情况划掉

我们考虑当前怎么去写dp状态转移方程式

我们首先来想dp表达式表达的是什么，我们的dp[i][j]表示的是剩下i只白鼠，j只黑鼠，公主能够获胜的概率

我们来根据上面的三种情况，对dp进行转移，

dp[i][j]+=i/(i+j)//先手直接拿到白色

dp[i][j]+=j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2]//第三种情况

dp[i][j]+=j/(i+j)*(j-1)/(i+j-1)*(-2)/(i+j-2)*dp[i][j-3]//第四种情况

#include<bits/stdc++.h>
using namespace std;
#define double long double 
int w,b;
double dp[1005][1005];
signed main()
{cin>>w>>b;for(int i=1;i<=w;i++){dp[i][0]=1.0;}for(int i=1;i<=b;i++){dp[0][i]=0.0;}for(int i=1;i<=w;i++){for(int j=1;j<=b;j++){dp[i][j]+=(double)i/(i+j);//先手取白色if(j>=2)dp[i][j]+=(double)j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2];if(j>=3)dp[i][j]+=(double)j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3];}}cout<<fixed<<setprecision(9)<<dp[w][b]<<'\n';return 0;
}

football

我莫名奇妙进不去poj了，只能简述一下题意了，我们来分析一下题目，这个n的数据范围为8，那我们也就是最大只有128个队伍，因此我们可以考虑到最大时间复杂度也许可以为O(n^3)，我们来考虑一下dp的含义，我们可以用dp[i][j]去表示第i轮j获胜的概率，我们现在来考虑一下状态转移方程式

我们首先考虑两个人是否会在第i轮相遇，如果说一个人在左子树，一个人在右子树就可以碰到，那么我们只需要判断两个人先除以(1<<n)判断是否在一个父节点上，如果在的话，那么值应该是一样的，然后除以(1<<(n-1))判断是否在不同的子树上，如果在不同子树，那么值是不一样的

这样就可以O（1）的判断了

那么我们来考虑状态转移方程式

当前第i轮j获胜的概率=第i-1轮j获胜的概率*第i-1轮k获胜的概率*j战胜k的概率，就是状态转移方程式

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
double a[130][130];
double dp[10][130];
void solve(int n)
{for (int i = 0; i < (1 << n);i++)dp[0][i] = 1.0;for (int i = 0; i < (1 << n); i++){for (int j = 0; j < (1 << n); j++){cin >> a[i][j];}}for (int i = 1; i <= n;i++){for (int j = 0; j < (1 << n);j++){for (int k = 0; k < (1 << n);k++){if(j/(1<<i)==k/(1<<i)&&j/(1<<(i-1))!=k/(1<<(i-1))){dp[i][j] += dp[i - 1][j] * dp[i - 1][k] * a[j][k];}}}}int flag = 0;double maxn = 0;for (int i = 0; i < (1 << n);i++){if(dp[n][i]>maxn){maxn = dp[n][i];flag = i;}}cout << flag + 1 << "\n";
}signed main()
{while (cin >> n&&n!=-1){solve(n);}return 0;
}

D. Bag of mice

football

相关文章：