什么是概率DP？

一、概率DP

顾名思义，概率DP就是动态规划求概率的问题。一般来说，我们将dp数组存放的数据定义为到达此状态的概率，那么我们初值设置就是所有初始状态概率为1，最终答案就是终末状态dp值了。

我们在进行状态转移时，是从初始状态向终末状态顺推，转移方程中大致思路是按照当前状态去往不同状态的位置概率转移更新DP，且大部分是加法。

二、期望DP

用于求解期望的DP。这类问题一般将dp数组存放的数据定义为到达终态还需要的期望值。那么初值设置就是终末状态期望为0，答案就是初始状态的dp值了。

我们在进行状态转移时，一般是从终末状态逆推到起始状态，转移方程大致思路是找到当前状态所有可以转移到的状态，将它们的期望依概率相加即可。这是对于不同行动有概率的情况，比如投骰子。但对于多种情况互斥可选的时候(一般题目会告知你取最优策略)，比如飞行棋投骰子/钻隧道二选一移动，这时可能就需要取max或min来转移了。

三、总结的规律：

1. 期望可以分解成多个子期望的加权和，权为子期望发生的概率，即 E(aA+bB+…) = aE(A) + bE(B) +…+1；

2. 期望从后往前找，一般dp[n]=0，dp[0]是答案；

3. 解决过程，找出各种情况乘上这种情况发生的概率，求和。