(错排问题) 递推法

问题描述

共有n个velopes和n个letters, 其中每个第i号letter对应于第i号veilope. 我们需要确定总共有多少种不同的排列方式, 以确保没有一封信被错误地放入其对应的envelope中.

思路

通过递推的方法来解决这个问题。
当n封信与n个信封的数量相同时（即有n个不同的信和同样数量的信封），错位排列的数量可以用f(n)来表示。
假设将第n封信放入第i个信封中（其中i的取值范围是1到n-1）。
那么接下来会出现两种情况：

将第i 封信放入第n 个信封盒中：那么剩余的 封信与 封信箱中还剩 下 n-2 个编号。这些剩下的 封信用错位方式排列

在编号为i的第n个信箱中未放置对应的第i号邮件，在这种情况下剩余的信箱与邮件总数均为n-1，并且其中对应的第i个信箱与第n个邮件已经被确定不放。有趣的是受限于这种情况，在剩下的n-1个信箱中无法放置原本属于第i个信箱的那封邮件，并且实际上构成了一个数目为n - 1的错位排列f(n -1)

因为 i 可以取 [1, n-1]， 那么可以得到递推公式 ： f(b) = (n - 1) * ( f(n -1) + f(n - 2))。

对于边界情况， f(1) = 0， f(2) = 1.

代码

    #include <bits/stdc