我在做洛谷题目，是这样的：

错排公式大法

题目描述

考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 $n$个元素的错排数记为$D(n)$。

则有这样一个公式$D(n)=(n-1) * (D(n-1)+D(n-2))$。其中$D(1)=0,D(2)=1$。

现在给出你个整数$n$，你需要告诉我$D(n)$的值。

输入格式

一行一个整数$n(1<=n<=1000)$。

输出格式

输出一个整数-表示D(n)的值。

样例 #1

样例输入 #1

3

样例输出 #1

2

我做的代码：

#include
using namespace std;
int d(int a)
{
    if (a==1)
    {
        return 0;
    }
    else if (a==2)
    {
        return 1;
    }
    return (a - 1) * (d(a - 1) + d(a - 2));
}
int main()
{
    int a;
    cin >> a;
    cout << d(a);
    return 0;
}

但是超时了，不知怎么优化

求助，在线等急