思路:用dp[i][j]表示在i,j点的期望步数，p[i][j][k](k=0-2)表示i,j点的3个概率，假设所有期望都是已知：
则dp[i][j]=p[i][j][0]*(dp[i][j]+2)+p[i][j][1]*(dp[i][j+1]+2)+p[i][j][2]*(dp[i+1][j]+2);
由于p[i][j][0]+p[i][j][1]+p[i][j][2]=1为了方便表示，可以把2提出来写成:
dp[i][j]=p[i][j][0]*dp[i][j]+p[i][j][1]*dp[i][j+1]+p[i][j][2]*dp[i+1][j]+2;
现在等号左右两边都有dp[i][j],移项得:
dp[i][j]=(p[i][j][1]*dp[i][j+1]+p[i][j][2]*dp[i+1][j]+2)/(1-p[i][j][0]);
现在解法很明显了，要求dp[i][j]，先知道dp[i+1][j]和dp[i][j+1]即可，由于dp[r-1][c-1]是已知的0，所以倒推即可得到所有的dp[i][j].
Read full article from 概率dp入门篇 - 破晓べ - 博客园
No comments:
Post a Comment