类型：概率DP
题意：有N个箱子放有礼物，M个人依次取。如果取到的箱子有礼物，则拿走礼物。无论有没有拿到礼物，都将箱子原状放回。（所以就有可能后面的人拿到前面的人拿过的箱子，然后就没得到奖品）。问，主办方期望送出的礼物数量。
思路：
思路一：期望递推法。
期望是理想值。可以理解成，在理想状态下，做期望数次，一定，也是恰好，能完成这件事。
为什么能这么想？在现实中显然是不成立的，但是我们是做题目，求的是一个理想的值，也就是说我们是在一个理想的环境中，所以可以用这种理想化的想法。
那么这道题目就是：设dp[i] 表示i个人拿过以后，主办方送出礼物的期望数量。
那么，对于第i个人，可能拿到，也可能没拿到礼物，转移方程就是：
dp[i] = (N-dp[i-1])/N * (dp[i-1] + 1) + (dp[i-1])/N * dp[i-1];
拿到的概率 拿到的话就要多送一个 没拿到的概率 没拿到那还是一样
出口是：dp[0] = 0; dp[1] = 1; 不解释……
太神奇了（会不会是碰巧对的呢……奇葩思路）
思路二：（别人） 从概率角度。
设dp[i] 表示 第i个人拿到奖品的概率。则
dp[i] = (1-dp[i-1])*dp[i-1] + dp[i-1] * (dp[i-1] - (1.0/n))
意义为:如果个人没拿到，则本次拿到概率和前次相同。如果前个人拿到了，那么本次拿到的概率应当比上次小(1/n)
代码（思路一）：
#include <cstdio> #include <cstdlib> #define M 100010 double dp[M]; int main() { int n, m; while (~scanf("%d%d", &n, &m)) { dp[0] = 0; dp[1] = 1; for (int i = 2; i <= m; i++) { dp[i] = (n-dp[i-1])/(n+0.0)*(dp[i-1]+1) + (dp[i-1])/(n+0.0)*dp[i-1]; } printf("%.9lf ", dp[m]); } return 0; }