概率dp一般正着递推，即dp[i]：表示到达状态i的答案，最后的答案是dp[n]。
期望dp一般逆着推，即dp[i]：表示到达状态i还差多少，最后的答案是dp[0]。
叉姐在post上有回答提及。
概率dp一般正着递推，即dp[i]：表示到达状态i的答案，最后的答案是dp[n]。
期望dp一般逆着推，即dp[i]：表示到达状态i还差多少，最后的答案是dp[0]。
叉姐在ICPCCamp.post上的回答也有所提及。
涂格子1
n个格子，每次随机涂一个，求涂满m个格子的期望次数。
解法：
- 定义 $dp_i$：表示已经涂了 $i$ 个还需要的期望次数
- 转移：$dp_i=dp_{i+1}+\frac{n}{n-i}$(其中$\frac{n}{n-i}:$因为$i$到$i+1$一定要涂一个，此次满足几何分布的数学期望，因此可得)
- 另一种得到公式的思考方式：$dp_i=\frac{i}{n}dp_i+\frac{n-i}{n}dp_{i+1}+1$，化简后与上式相同。
涂格子2
n个格子，每次随机涂一个，求涂m次后期望涂色格子数。
解法
- 定义$dp_i:$ 表示涂了 $i$ 次后的期望个数
- 转移：$dp_i=\frac{n-dp_{i-1}}{n}+dp_{i-1}$
麻球繁衍
开始有 $n$ 个麻球，每天每个麻球会死亡，同时繁衍出若干新麻球。每个麻球繁衍 $i$ 个麻球的概率是 $p_i (0≤i<k)$。求在 $m$ 天内麻球死绝的概率。
解法
- 每个球相互独立，故分别考虑每一个在 $m$ 天 内死绝的概率$f_m$，答案即为$f_m^n$。
- 对于每一个麻球 $f_i=\sum_{j=0}^{k-1}p_j·f_{i-1}^j$
- 递推算即可