题意：
给你一个R行C列的矩阵，最开始你在(1,1) 位置，你需要走到(R,C)
在(i,j)(1<=i<=R , 1<=j<=C)位置，你可以花费2魔法传送(i,j)、(i,j+1)、(i+1,j)
题目会依次给你从(i,j)位置传送到这三个位置的概率a,b,c
问你从(1,1)走到(R,C)消耗魔法的期望次数
题解：
大部分概率dp都是倒推，那我们也这样试试
我们设dp[i][j]：你现在在(i,j)位置，你走到(R,C)消耗魔法的期望次数
dp[i][j]=a*dp[i][j]+b*dp[i][j+1]+c*dp[i+1][j]+2
如果某个位置的概率a等于1，就不用管这个位置了
代码：
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> using namespace std; #define mem(a) memset(a,0,sizeof(a)) typedef long long ll; const int maxn=1005; const int INF=1e9; const double blo=(1.0+sqrt(5.0))/2.0; const double eps=1e-8; struct shudui { double a,b,c; }que[maxn][maxn]; double dp[maxn][maxn]; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { scanf("%lf%lf%lf",&que[i][j].a,&que[i][j].b,&que[i][j].c); } } mem(dp); //dp[1][1]=1.0; for(int i=n;i>=1;--i) { for(int j=m;j>=1;--j) { if(i==n && j==m) continue; if(1.0-que[i][j].a<eps) continue; dp[i][j]=(dp[i][j+1]*que[i][j].b+dp[i+1][j]*que[i][j].c+2.0)/(1.0-que[i][j].a); } } printf("%.3lf\n",dp[1][1]); } return 0; }
原文：https://www.cnblogs.com/kongbursi-2292702937/p/13656049.html