SPOJ1026 Favorite Dice & 赠券收集问题

我们考虑当你手上已有 $i$ 种不同的数，从集合中任选一个数得到新数的概率，为$\frac{n-i+1}{n}$，那期望即为$\frac{1}{p} = \frac{n}{n-i+1}$。所以总期望为$\sum_{i = 1}^{n}\frac{n}{n-i+1} = \sum_{i=1}^{n}\frac{n}{i}$。

当然也可以用概率 dp 来推：

我们设 $f[i]$ 表示取了 $i$ 种数时还须取的数的期望。

显然$f[n] = 0$，答案为$f[0]$，所以为逆推。

又由于选第 $i$ 个数后再选一个数与已经选过的数不同的概率为$\frac{n-i}{n}$，相同为$\frac{i}{n}$。

于是可得$f[i] = \frac{n-i}{n}f[i+1]+\frac{i}{n}f[i] + 1$。

解得$f[i] = f[i+1] + \frac{n}{n-i}$。

于是整理一下就变成了$f[0] = \sum_{i=1}^{n}\frac{n}{i}$。