3月24日 装错信封

3.5 Problem E: 深入浅出学算法031-装错信封
任务内容
清明时节雨纷纷， 写封信件祭先人。 无奈信件实在多， 错装信封把信混。 现写了n封信和n个信封，把所有的信都装错信封的情况共有多少种？
Input
多组测试数据，每组输入1个整数n （10 >= n >=2).
Output
对于每组测试数据输出一行，值为所有的信都装错信封的情况种数？

本题是错位重排问题，Dn=(n-1)*(Dn-1+Dn-2)，从第一封信开始，从第四封信开始，第三封信和第二封信的和，从一封信开始没有装错的情况，从第二封信开始只有1种情况，以后找到递推式求解。

#include <stdio.h>
int main()
{
    int n;
    long long dp[100]={0,0,1};
    for(int i=3;i<21;i++){
        dp[i]=(i-1)*dp[i-1]+dp[i-2];
    }
    while(scanf("%d",&n)!=EOF,n){
        printf("%ld\n",dp[n]);
    }
    return 0;
}