i + 1][j] * p[2][i][j]) / (1.0 - p[0][i][j])
从这个转移方程不难看出从dp[r][c]向前推就行了，dp[r][c] = 0，还有要注意分母为0的情况要特判，如果p[0][i][j] ＝ 1，则显然是个死循环，dp[i][j] = 0
#include
#include
int const MAX = 1005; double const EPS = 1e-10; double p[3][MAX][MAX], dp[MAX][MAX]; int main() { int r, c; double p1, p2, p3; 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[0][i][j], &p[1][i][j], &p[2][i][j]); dp[r][c] = 0; for(int i = r; i >= 1; i--) for(int j = c; j >= 1; j--) if(!(i == r && j == c)) if(fabs(p[0][i][j] - 1.0) < EPS) dp[i][j] = 0; else dp[i][j] = (dp[i][j + 1] * p[1][i][j] + dp[i + 1][j] * p[2][i][j] + 2) / (1.0 - p[0][i][j]); printf("%.3f\n", dp[1][1]); } }