题目描述：

一个n面的骰子，求期望掷几次能使得每一面都被掷到。

题解：

先谈一下期望DP.

一般地，如果终止状态固定，我们都会选择逆序计算.

很多题目如果顺序计算会出现有分母为 0 的情况，而逆序计算中则不会出现.

比如，对于本题，我们设状态 $F_{i}$ 表示当前已翻过 $i$ 种不同的面，为了翻完每个面还需要额外翻的期望次数.

终止状态： $F_{n}=0$ 

考虑枚举到 $F_{i}$ ，那么当前翻到的面有两种可能.

$1.$ 先前被翻过，那么该概率是 $P_{1}=\frac{i}{n}$，还需翻的次数为 $tot_{1}=1+F_{i}$ .

$2.$ 先前未被翻过，概率为 $P_{2}=\frac{n-i}{n}$，次数为 $tot_{2}=F_{i+1}+1$.

列等式：

$F_{i}=P_{1}\times tot_{1}+P_{2}\times tot_{2}$ .

带入，化简得 $F_{i}=\frac{n}{n-i}+F_{i+1}$ 

Code:

#include 
     
      #define setIO(s) freopen(s".in","r",stdin) #define maxn 20000 using namespace std;double F[maxn]; int main(){    // setIO("input");     int T;     scanf("%d",&T);     while(T--)    {        int n;         scanf("%d",&n);         F[n] = 0.00;                         for(int i = n - 1; i >= 0; --i)         {            F[i] = (double)1.0*(1.0*n/(n-i)*1.0) + F[i + 1];              }        printf("%.2f\n",F[0]);     }    return 0; }