昨天那道题大家做法不一。
有人爆搜，有人大型分类讨论。
但递推呢？
原题：
有6个箱子A-F，每个箱子里有一把钥匙，拿到钥匙i就能打开箱子i。现在我们强行打开1,2箱子，取出里面的钥匙，然后用这些钥匙打开其他箱子……最后问有几种可能打开所有箱子。
首先公式出来：
A[i] = (i - 1) * A[i - 1]
好接下来我们把这公式证明一下。
首先，我们不能讨论1号箱子。
因为这样我们就把题改了！
所以我们可以去讨论3,4,5,6号箱子，这里选择6号。
那我们如何讨论呢？
1. 6号装6号的钥匙，一定不行。
因为6装6的话除非你撬开它不然一定打不开。
2. 6号装x号的钥匙
那我们这是干一件事情：
把x号箱子里的钥匙和6号箱子里的钥匙（即x）调换，然后删掉6号箱子。
我们举个例子。
箱子：1 2 3 4 5 6
钥匙：* 6 * * * 4
此时6号箱子里装的是2号钥匙，我们把6号箱子里的钥匙（4号钥匙）和2号箱子里的钥匙（6号钥匙）调换，可得：
箱子：1 2 3 4 5 6
钥匙：* 4 * * * 6
然后把6号箱子删掉。
箱子：1 2 3 4 5
钥匙：* 4 * * *
原来我们是先用2号箱子里的6号钥匙打开6号箱子，然后用6号箱子里的钥匙打开4号箱子。
现在变成了用2号箱子直接打开4号箱子。
而这里有i - 1中可能（A[6]即是5种可能）。
然后经过变换后我们得到的不就是Ai - 1吗？
所以递推公式就是：
A[i] = (i - 1) * A[i - 1];
最后我们看一下A[2]是几。
先读一下题：
把1,2号箱撬开以求打开1,2号箱子。
这当然就是2中情况了。
所以：
A[3] = 2 * A[2] = 2 * 2 = 4;
A[4] = 3 * A[3] = 3 * 4 = 12;
A[5] = 4 * A[4] = 4 * 12 = 48;
A[6] = 5 * A[5] = 5 * 48 = 240;
这就是我们的正确答案：240!
好最后我们看一下代码。
#include<iostream>
#include<cmath>
using namespace std;
int A[20], n;
int main()
{
cin >> n;
A[2] = 2;
for(int i = 3; i <= 20; i ++) A[i] = (i - 1) * A[i - 1];
cout << A[n] << endl;
return 0;
}
+
+
%%%%
%%%%