概率DP是一种以概率为最优解的动态规划问题。求解概率时候的分步原理与动态规划中的状态转移类似。
所谓概率dp，用动态规划的思想找到一个事件中可能发生的所有情况，然后找到符合要求的那些情况数，除以总数便可以得到符合要求的事件发生的概率。其核心思想还是通过dp来得到事件发生的所有情况，很类似在背包专题中我们提及的组合记数问题。
学习：https://www.cnblogs.com/Paul-Guderian/p/7624039.html
例题：
1、POJ 3071 Football
求出最有可能的冠军的队伍dp[i][j]表示第j支队伍在第i轮比赛中获胜的概率p[i][j]=dp[i-1][j]*sum,sum=(sum)(dp[i-1][k]*p[j][k])
在i-1轮种获胜，并且打赢k的概率，并且要保证k在i-1轮中获胜
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
//概率DP
double p[130][130];
double dp[130][8];
int n;
// 求出最有可能的冠军的队伍
//dp[i][j]表示第j支队伍在第i轮比赛中获胜的概率
//dp[i][j]=dp[i-1][j]*sum,sum=(sum)(dp[i-1][k]*p[j][k])
//在i-1轮种获胜，并且打赢k的概率，并且要保证k在i-1轮中获胜
int main(){
while(scanf("%d",&n),n!=-1){
int m=(1<<n); //队伍数量
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
scanf("%lf",&p[i][j]);
}
dp[i][0]=1; //初始化
}
int ans;
for(int i=0;i<n;i++){ //利用2进制枚举状态
ans=0;
for(int j=0;j<m;j++){ //队伍数量
double sum=0;
for(int k=(1<<i);k<(1<<(i+1));k++){ //这个状态
sum+=dp[k^j][i]*p[j][k^j];
//对手在第i轮获胜的概率，j打败对手的概率
}
dp[j][i+1]=dp[j][i]*sum; //第一维是队伍标号啊，第二维才是比赛轮数
if(dp[j][i+1]>dp[ans][i+1]) ans=j;
}
}
printf("%d\n",ans+1);
}
return 0;
}
原文：https://www.cnblogs.com/shirlybaby/p/12615322.html