GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A28882. $公司为每个员工都准备了一张信纸，每个信纸都对应着一个写着员工名字的信封。如果所有的信纸都不小心装错了信封，求所有信纸都装错信封共有多少种不同情况?输入描述一个正整数n表示公司人数，保证n\leq20。输出描述一个整数，代表有多少情况样例1输入2输出1$

填空题中等

知识点

错排问题递推组合计数

题目描述

公司为每个员工都准备了一张信纸，每个信纸都对应着一个写着员工名字的信封。如果所有的信纸都不小心装错了信封，求所有信纸都装错信封共有多少种不同情况? 输入描述 一个正整数n表示公司人数，保证n\leq20。 输出描述 一个整数，代表有多少情况 样例1 输入 2 输出 1

参考答案

def ct(n):
    # 边界条件
    if n == 0:
        return 1
    elif n == 1:
        return 0
    
    # 动态规划数组
    D = [0] * (n + 1)
    D[0] = 1 
    D[1] = 0
    
    # 迭代计算D(n)
    for i in range(2, n + 1):
        D[i] = (i - 1) * (D[i - 1] + D[i - 2])
    
    # 返回D(n)
    return D[n]

# 输入
n = int(input())
print(ct(n))

上一题下一题