概率dp入门

概率DP主要用于求解期望、概率等题目。

转移方程有时候比较灵活。

一般求概率是正推，求期望是逆推。通过题目可以体会到这点。

poj2096:Collecting Bugs

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
typedef long long ll;
using namespace std;
#define mod 1000000007
double dp[][];
int n,s;
int main()
{
    while(scanf("%d%d",&n,&s)!=EOF)
    {
        dp[n][s]=;
        for(int i=n;i>=;i--)
        {
            for(int j=s;j>=;j--)
            {
                if(i==n&&j==s) continue;
                dp[i][j]=(n*s+i*(s-j)*dp[i][j+]+(n-i)*j*dp[i+][j]+(n-i)*(s-j)*dp[i+][j+])/(n*s-i*j);
            }
        }
        printf("%.4f\n",dp[][]);
    }
    return ;
}
//http://www.cnblogs.com/jackge/archive/2013/05/21/3091757.html

sdut2626题目： The number of steps

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
typedef long long ll;
using namespace std;
#define mod 1000000007
int n;
double dp[][];
double a,b,c,d,e;
int main()
{
    while(scanf("%d",&n)!=EOF&&n!=)
    {
        scanf("%lf%lf",&a,&b);
        scanf("%lf%lf%lf",&c,&d,&e);
        memset(dp,,sizeof(dp));
        dp[n][]=;
        for(int i=;i<=n;i++)
        {
            dp[n][i]=dp[n][i-]+;
        }
        for(int i=n-;i>=;i--)
        {
            for(int j=;j<=i;j++)
            {
                if(j==)
                {
                    if(i==n) continue;
                    dp[i][j]=dp[i+][j]*a+dp[i+][j+]*b+1.0;
                }
                else
                {
                   dp[i][j]=dp[i][j-]*e+dp[i+][j]*c+dp[i+][j+]*d+1.0;
                }
            }
        }
        printf("%.2lf\n",dp[][]);
    }
    return ;
}

HDU4405：

题目大意：

跳棋有0~n个格子，每个格子X可以摇一次色子，色子有六面p(1=<p<=6),概率相等，可以走到X+p的位置，有些格子不需要摇色子就可以直接飞过去。问从0出发到达n或超过n摇色子的次数的期望。

解题思路：

dp[i]表示从i出发到达最终位置的次数期望。

转移方程当i需要摇色子时，dp[i]=Σ(1+dp[i+j])(1<=j<=6);否则dp[i]=dp[jump[i]] 表示从i能够跳得到的最大位置。

预处理后面的6个位置，直接转移就行。

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <queue>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,m;
int path[];
double dp[];
int main()
{
    int xx,yy;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==&&m==) break;
        memset(path,-,sizeof(path));
        for(int i=;i<=m;i++)
        {
            scanf("%d%d",&xx,&yy);
            path[xx]=yy;
        }
        for(int i=n;i>=;i--)
        {
            if(path[i]!=-)
            {
                int j=path[i];
                if(path[j]!=-)
                    path[i]=path[j];
                else path[i]=j;
            }
        }
        for(int i=;i<;i++)
            dp[n+i]=;
        for(int i=n-;i>=;i--)
        {
            if(path[i]!=-)
                dp[i]=dp[path[i]];
            else
            {
                double tt=;
                for(int j=;j<=;j++)
                {
                    tt+=dp[i+j]*(1.0/6.0);
                }
                dp[i]=+tt;
            }
        }
        printf("%.4f\n",dp[]);
    }
    return ;
}