素养赛Python复赛题——错排问题

2023年北京赛区素养赛Python复赛题：
第6题，错排问题
题目描述:
圣诞节快到了，公司为每个员工都准备了礼物，每个礼物都有一个精美的盒
子。如果所有的礼物都不小心装错了盒子，求所有礼物都装错盒子共有多少种不
同情况。
输入描述:
输入一个正整数n表示公司人数，保证n≤20.
输出描述:
输出一个整数，代表有多少种情况。
样例1:
输入:
2
输出:
1

解析：
模拟：
n=1，有0种情况；
n=2，有1种情况；
n=3的时候，有两种情况：
3 1 2
2 3 1
n=4的时候，有9种情况
原定顺序是1 2 3 4
当1选择2的位置
2 1 4 3
4 1 2 3
4 1 3 2
当1选择3的位置
2 4 1 3
4 3 1 2
3 4 1 2
当1选择4的位置
2 3 4 1
3 4 2 1
4 3 2 1
动态转移方程f(n)表示n个礼物装错盒子，
第一反应感觉式子应该是如下：
第n个礼物装错盒子的选择有n-1种，f(n)=(n-1)f(n)
但是f(4)!=(4-1)f(3)
因为f(n)和f(n-1)之间还有一些差异在于，
因为第n个礼物一旦占据了n-1箱子中的第m号，
那么m号假定放置于n号箱子，现在开始错排，
假设m号不能放于n号，情况即为f(n-1)。
但是m号可以放于n号，当m放在n号的时候，存在f(n-2)。

def f(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return (n - 1) * (f(n - 1) + f(n - 2))


n = int(input())
print(f(n))