期望DP

期望DP概念

要求一个事件期望，有两种方法：

一种是根据概率公式，直接求： \[ E(x) = \sum_{i}^{n} x_i*P(x_i) \] 但是这样写程序一般会超时。

另一种更常见的做法是根据期望的递归公式， \[ E(x) = F(E(x-1)) \] 来逐步推出所要求的期望值。

买卡片1

卡片一共有k种，现在要买n张卡片，买到每种卡片的概率相同，求 买到卡片种类数 的期望。

首先，假设只买1张卡片，期望肯定为1，因为无论买哪张都是新的种类。

然后，假设我们已经知道 买i-1张卡片，得到的种类数期望, 那么再买到一张的新卡片的期望为 (k - E(i-1)) / k（因为x为1，期望和概率相同）。

设 买i张卡片，得到的种类数 为 DP{i} , 有 \[ dp[i] = dp[i-1] + \frac{k - dp[i-1]}{k} \] 即：买 i 张得到种类数的期望 = 买i-1张...的期望 + 再获得一张新卡片的期望

cin>>n>>k;
dp[1] = 1;
for(int i = 2 ; i <= k ; i ++){
    dp[i] = dp[i-1] + 1.0*k/(k - i+1);
}
cout<<fixed<<setprecision(6)<<dp[k];

买卡片2

卡片一共有k种，买到每种卡片的概率相同，现在需要不断地购买，求 买到k种所需要次数 的期望。

首先，假设只买1张卡片，期望为1，因为无论买哪张都是新的种类。

然后，假设目前到手 i-1 种，那么接下来，每次购买，买到第 i 种的概率P == (k - i + 1)/k，那么所需要次数的期望，就是 1/P == k/(k - i +1)。

由此，我们得到递推式： \[ dp[i] = dp[i-1] + \frac{k}{k-i+1} \] 代码：

cin>>n>>k;
dp[1] = 1;
for(int i = 2 ; i <= k ; i ++){
    dp[i] = dp[i-1] + 1.0*k/(k - i+1);
}
cout<<fixed<<setprecision(6)<<dp[k];