概率与期望 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;
}