SP1026 FAVDICE

题目描述：
一个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} imes tot_{1}+P_{2} imes tot_{2}$ .

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

Code:

#include <bits/stdc++.h>
#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
",F[0]); 
    }
    return 0; 
}