此题的递归关系的分析很有难度。可以借助人来选帽子的情景这么分析：
考虑dp[n]。假设第一个人选择了第i顶帽子（除去第1顶不能选，他共有n-1种选择）。OK，接下来如何呢？对于第i个人（注意这个i是和第一个人的选择对应的），此时有两种选择：
- 第i个人选择了第1顶帽子。则剩下的人的编号和帽子的编号
人: 2,3,4,...,i-1,i+1,...,n
帽子: 2,3,4,...,i-1,i+1,...,n
要使得任意第k个人不拿与自己编号相同的帽子，这就相当于dp[n-2]的问题。
- 第i个人不选择第1顶帽子。则剩下的人（包括第i个人，因为他还么确定）的编号和帽子的编号
人: 2,3,4,...,i-1,i,i+1,...,n
帽子: 2,3,4,...,i-1,1,i+1,...,n
要使得任意第k个人不拿与自己编号相同的帽子（同时第i个人不能拿第一顶帽子），这就转化为了dp[n-1]的问题。
综上，加上考虑到第一个人选择第i顶帽子有n-1种选择，每种选择的后续分析都是一模一样的，故总的递推关系是：
dp[n] = (dp[n-1]+dp[n-2])*(n-1)