这道题一开始自己没想到用动态规划去做，后面看了下大佬们的解法，才发现原来还可以动态规划去做。
首先讲下我这种解法吧：
1.这是概率论中一道典型的配对模型
所谓配对模型就是，比如n个人任取n顶不同的帽子，n把钥匙随机开n把锁，求至少有一对配对成功的几率。
对应这种配对问题，存在着一个公式，
全部配对错误的可能性为：
1/2!-1/3!-...+(-1)^(n-1)*1/n!
利用这个公式我们便可以对问题进行求解

#include<bits/stdc++.h>
using namespace std;
void Help(int n)
{
    double a=1;
    double b=2;
    double i=2;
    double sum=0;
    while(i<=n)
    {
        sum+=a*(1/b);
        b*=i+1;
        a=-a;
        i++; 
    }
    sum*=100;
    cout<<setiosflags(ios::fixed)<<setprecision(2)<<sum<<"%"<<endl;

}

int main()
{
    int m;
    while(cin>>m)
    {
        Help(m);
    }
}

对于第二种解法而言：
假设a的名字没有被a拿到，其他n - 1个人都有可能拿到，即有n - 1种情况。假设b拿到了a的名字，那么对于b的名字有两种情况， 第一种是b的名字被a拿到了，也就是a、b互相拿到了对方的名字，那么对于其他n - 2个人互相拿错又是一个子问题f(n - 2). 第二种是b的名字没有被a拿到，则剩下的问题是子问题f(n - 1).因此可得递推公式f(n) = (n - 1) * (f(n - 1) + f(n - 2)). 最终得出公式n人都不获奖的概率h(n) = (n - 1) * (f(n - 1) + f(n - 2)) / (n!)

#include<bits/stdc++.h>
using namespace std;
long long  dp[1007];
double Help(int m)
{
    if(dp[m]!=0) return dp[m];
    else return dp[m]=(m-1)*(Help(m-1)+Help(m-2));
}
int main()
{
    int m;
    memset(dp,0,sizeof(dp));
    dp[1]=0;
    dp[2]=1;
    dp[3]=2;
    while(cin>>m)
    {
        double g=Help(m);
        for(int i=1;i<=m;i++)
        {
            g=g/i;
        }
        g*=100;
        cout<<setiosflags(ios::fixed)<<setprecision(2)<<g<<"%"<<endl;
    }
}