题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3853
题意：
有一个n*m的网格。
给出在每个格子时：留在原地、向右走一格，向下走一格的概率。
每走一格会消耗2点体力。
问你从(1,1)到达终点(n,m)消耗体力的期望。
题解：
表示状态：
dp[i][j] = rest steps（剩余路程花费体力的期望）
i,j：现在的位置
找出答案：
ans = dp[0][0]
如何转移：
期望dp的套路：考虑子期望。。。
now: dp[i][j]
能转移到的子期望：dp[i][j]（留在原地）,dp[i][j+1]（向右）,dp[i+1][j]（向下）
dp[i][j] = dp[i][j]*trans[i][j][0]
+ ( dp[i][j+1]*trans[i][j][1]
+ dp[i+1][j]*trans[i][j][2] + 2 )
移项：
dp[i][j] = ( dp[i][j+1]*trans[i][j][1]
+ dp[i+1][j]*trans[i][j][2] + 2 )
/ (1-trans[i][j][0])
边界条件：
dp[n-1][m-1] = 0
到达终点后不用再耗体力。
注：（1）对于所有越界的概率应看成0。
（2）除法要保证除数不为0。
AC Code:
// state expression:
// dp[i][j] = rest steps
// i,j: present pos
//
// find the answer:
// ans = dp[0][0]
//
// transferring:
// now: dp[i][j] -> dp[i][j], dp[i+1][j], dp[i][j+1]
// dp[i][j] = dp[i][j]*trans[i][j][0]
// + (dp[i][j+1]*trans[i][j][1]
// + dp[i+1][j]*trans[i][j][2] + 2)
// dp[i][j] = (dp[i][j+1]*trans[i][j][1]
// + dp[i+1][j]*trans[i][j][2] + 2)
// / (1-trans[i][j][0])
//
// boundary:
// dp[n-1][m-1] = 0
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1005 using namespace std; int n,m;
double dp[MAX_N][MAX_N];
double trans[MAX_N][MAX_N][]; void read()
{
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
for(int k=;k<;k++)
{
scanf("%lf",&trans[i][j][k]);
}
}
}
} void solve()
{
memset(dp,,sizeof(dp));
for(int i=n-;i>=;i--)
{
for(int j=m-;j>=;j--)
{
if(i==n- && j==m-) continue;
if(trans[i][j][]==1.0) continue;
dp[i][j]=(dp[i][j+]*trans[i][j][]+dp[i+][j]*trans[i][j][]+2.0)/(1.0-trans[i][j][]);
}
}
} void print()
{
printf("%.3f\n",dp[][]);
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
read();
solve();
print();
}
}