昨天看了看概率DP的题，主要都是在推公式。状态转移方程是把该状态分成disjoint sample space，再向后转移。
dp[i][j]常用于该状态到最终状态的期望值，所以状态向后转移。
这里面，dp[i,j]=2+p[i,j,0]*dp[i,j]+p[i,j,1]*dp[i,j+1]+p[i,j,2]*dp[i+1,j]
+2是因为只要要进行选择，无论结果如何，一定会消耗2 energy，然后下一步可能在[i,j],[i+1,j],[i,j+1]
这一题也可以记忆化搜索，直接从后向前递推也OK。
之前WA了一次是因为少了特判p[i][j][0]=0，因为出现在分母上，我print了一下发现如果分母=0那个dp[i][j]就不会输出==
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;
//hdu 3853
int R;
int C;
const int maxn=1010;
double p[maxn][maxn][3];
double dp[maxn][maxn];
void run()
{
memset(dp,0,sizeof(dp));
dp[R][C]=0;
for(int i=R;i>=1;i--)
{
for(int j=C;j>=1;j--)
{
if(i==R&&j==C) continue;
if(p[i][j][0]==1) continue;//因为下面有除法，所以要特判分母=0的case
dp[i][j]=(2+p[i][j][1]*dp[i][j+1]+p[i][j][2]*dp[i+1][j])/(1-p[i][j][0]);
//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
}
printf("%.3lf\n",dp[1][1]);
}
int main()
{
freopen("input.txt","r",stdin);
// freopen("data.txt","r",stdin);
//freopen("out1.txt","w",stdout);
while(scanf("%d %d",&R,&C)!=EOF)
{
for(int i=1;i<=R;i++)
{
for(int j=1;j<=C;j++)
{
scanf("%lf %lf %lf",&p[i][j][0],&p[i][j][1],&p[i][j][2]);
}
}
run();
}
return 0;
}