本文主要是介绍错排，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

错排

次次做，次次忘，次次WA

问题描述：

n个人，n个帽子，每个人对应唯一的一顶帽子。问使得每个人都戴着不属于自己的帽子的方案数。

解题思路

设\(Dp[i]\) 表示i个人错排的方案，则转移方程为\(Dp[i] = (n-1)*(Dp[i-1] + Dp[i-2])\)

考虑，前i个已经错排好了，现要新加入第i+1个。

将第i+1个放到第k个的位置上(1<=k<=i),方案数为i

现在考虑第k个怎么放。

1. 放到第i+1的位置上，剩下i-1个人进行错排，方案数为 \(Dp[i-1]\)

2. 不放到第i+1的位置上，这时将第i+1的位置看作第k的位置，（第k个元素不能放到第k个位置也不能放到第i+1个位置上，这点是相同的）方案数为\(Dp[i]\)

故转移方程为\(Dp[i+1] = i * (Dp[i-1] + Dp[i])\)

这篇关于错排的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！