概率DP实例讲解

在动态规划中，概率DP一般会用于研究有关于概率，步数，期望等问题。

简单总结为以下四个点：

（1）数学期望 P=Σ每一种状态*对应的概率。

（2）因为不可能枚举完所有的状态，有时也不可能枚举完，比如抛硬币，有可能一直是正面，etc。 但是现在发现大多数题就是手动找公式或者DP推出即可，只要处理好边界，然后写好方程，代码超级简短。与常规的求解不同，数学期望经常逆向推出。

（3）比如常规的dp[x]可能表示到了x这一状态有多少，最后答案是dp[n]。而数学期望的dp[x]一般表示到了x这一状态还差多少，最后答案是dp[0]。

（4）什么时候可以互相计算呢？关键在于所求期望的变量值是否会随着过程变化而变化！！！而不仅仅和所处位置有关！！！这种情况下，我们可以记录到当前状态所需的步数，最后就可以算期望。

例题一：涂格子

n个格子，每次随机涂一个，求涂m次后期望涂色格子数。

如概述所说，设计状态f[i]表示涂i次后的答案。转移时考虑这次是涂了的还是没涂的。

转移方程为

另外，可证明

例题二：小孩和礼物

有n个礼物盒和m个小孩，每个盒子里有一个礼物。所有人轮流开盒子，每次打开一个随机盒子，如果里面有礼物就拿走（如果被开过了就没有礼物了）。问所有人拿走礼物的期望数量。

一个礼物=一个打开过的盒子。f[i]表示i个人拿走礼物的期望，相当于表示涂i次期望涂色格子数量。同涂格子2。

例题三：亚瑟王的生日庆典

亚瑟王过生，他每天抛一枚硬币，正面向上的概率是p。办庆典要花钱，在第i天要花(2i−1)千元。求正面向上数≥k次时的期望花钱数。

f[i]表示正面向上i次的期望花钱。转移时考虑是否掷到正面，容易列出转移f[i]=(1−p)f[i]+pf[i−1]+正面向上i次当天期望花费。

需要计算g[i]表示正面向上i次的期望天数，则当天期望开销=2×g[i]−1。g[i]=(1−p)g[i]+pg[i−1]+1。