昨天看了看概率DP的题,主要都是在推公式。状态转移方程是把该状态分成disjoint sample space,再向后转移。
dp[i][j]常用于该状态到最终状态的期望值,所以状态向后转移。
这里面,dp[i,j]=2+p[i,j,0]*dp[i,j]+p[i,j,1]*dp[i,j+1]+p[i,j,2]*dp[i+1,j]
+2是因为只要要进行选择,无论结果如何,一定会消耗2 energy,然后下一步可能在[i,j],[i+1,j],[i,j+1]
这一题也可以记忆化搜索,直接从后向前递推也OK。
之前WA了一次是因为少了特判p[i][j][0]=0,因为出现在分母上,我print了一下发现如果分母=0那个dp[i][j]就不会输出==
#incl......
阅读全文