期望概率DP简单题
从[1,1]点走到[r,c]点,每走一步的代价为2
给出每一个点走相邻位置的概率,共3中方向,不动: [x,y]->[x][y]=p[x][y][0] , 右移:[x][y]->[x][y+1]=p[x][y][1]; 左移:[x][y]->[x+1][y]=p[x][y][2];
问最后走到[r,c]的期望
dp[i][j]为从[i][j]点走到[r][c]的期望
有方程:
dp[i][j]= (dp[i][j]+2)*p[i][j][0] + (dp[i][j+1]+2)*p[i][j][1] + (dp[i+1][j]+2)*p[i][j][2] ;
移项合并: dp[i][j]= ( (dp[i][j+1]+2)*p[i][j][1] + (dp[i+1][j]+2)*p[i][j][2] + p[i][j][0]*2 ) / (1-p[i][j][0])
特判p[i][j][0]==1 的情况
#include "stdio.h"
#include "string.h"
#include "math.h"
double p[1010][1010][3],dp[1010][1010]; int main()
{
int n,m,i,j; while (scanf("%d%d",&n,&m)!=EOF)
{
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
scanf("%lf%lf%lf",&p[i][j][0],&p[i][j][1],&p[i][j][2]); memset(dp,0,sizeof(dp)); for (i=n;i>=1;i--)
for (j=m;j>=1;j--)
{
dp[i][j]=(dp[i][j+1]+2)*p[i][j][1]+(dp[i+1][j]+2)*(p[i][j][2])+p[i][j][0]*2;
if (fabs(p[i][j][0]-1)<=0.00000000001) dp[i][j]=0;
else dp[i][j]/=(1-p[i][j][0]);
}
printf("%.3lf\n",dp[1][1]);
}
return 0;
}