概率与期望DP


题意:给定一个矩阵,从(1,1)出发,有一定几率留在原地、向下走,向右走,求走到(r,c)平均要走多少步(每次移动算两步)?

注意有可能有的格子没有几率向下向右走


思路:设f[i][j]为(i,j)走到(r,c)的期望步数,p[i][j][k]为(i,j)向方向k的移动几率,那么

f[i][j]=f[i+1][j]×p[i][j][1] + f[i][j+1]×p[i][j][2] + f[i][j]*p[i][j][3] + 2

由于我们要从f[i+1][j],f[i][j+1]推出f[i][j],所以经过移项:

f[i][j]=(f[i+1][j]×p[i][j][1] + f[i][j+1]×p[i][j][2] + 2)/(1-p[i][j][3]);

然而,为什么我们不能设f[i][j]为走到(i,j)的期望步数而从f[i-1][j],f[i][j-1]退出f[i][j]呢?因为你不知道出现在(i,j-1)的概率是多少,因此递推的过程将是不完备、不稳定、不正确的。然而如果像这篇博客里的一样,倒这递推,你只需要考虑从(i,j)走到后面两个点的概率,于是这是一个基于事实的递推:f[i][j]建立在后续点到达概率已知的基础上。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define MX 1001

using namespace std;
double f[MX][MX],p[MX][MX][4],r,c;

int main()
{
    double s;
    while(cin>>r>>c)
    {
        for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)scanf("%lf%lf%lf",&p[i][j][1],&p[i][j][2],&p[i][j][3]);
        f[r][c]=0;
        for(int i=r;i>=1;i--)
            for(int j=c;j>=1;j--)
            {
                if(i==r&&j==c||p[i][j][1]==1)continue;
                f[i][j]=(f[i+1][j]*p[i][j][3]+f[i][j+1]*p[i][j][2]+2)/(1-p[i][j][1]);
            }
        printf("%.3f\n",f[1][1]);
    }
    return 0;
}
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *