头条视频面试遇到一道题目

查到一种递归的思想！！！ 设长度为n的序列的全错位排列一共有f(n)种，假设我们已经解决了f(1)到f(n-1)，那么当序列新增了一个元素an，显然全错位排列中该元素不能放在第n个位置上，假设该元素在从1到n-1的第i个位置，那么在新序列中第n个位置上的元素可能有两种情况： 第n个位置上的元素为ai  因为an和ai都不在原位置上，因此只需剩余的元素都是全错位排列，新序列就构成了全错位排列。那么除去ai和an还剩下n-2个元素，则这n-2个元素一共有f(n-2)种全错位排列，因为i的选择共有n-1种，因此该情况下一共有(n-1)*f(n-2)种全错位排列。 第n个位置上的元素不为ai  该种情况相当于，前n-1个元素做好了全错位排列，an与其中任意元素交换位置，新生成的序列也是一个全错位排列。这种情况下i的选择共有n-1种，n-1的元素的全错位排列共有f(n-1)种，因此该情况下一共有(n-1)*f(n-1)种全错位排列。 综合以上两种情况，f(n)=(n-1)f(n-2)+(n-1)*f(n-1)=(n-1)[f(n-2)+f(n-1)]  显然这个公式适用于n>2的情况，而f(1)=0,f(2)=1是之前已经列举得出的。  将n=3代入，得到f(3)=2*(0+1)=2，将n=4代入，得到f(4)=3*(1+2)=9，与列举所得到的结果相同。

//这属于完全错排问题 int totalWrong(int n) {     vector<int>dp(n+1,0);     dp[1]=0;dp[2]=1;     for(int i=3;i<=n;++i)         dp[i]=(i-1)*(dp[i-1]+dp[i-2]);     return dp[n]; } //可以看看只跟前两个变量值有关，所以可以使用两个变量来节省空间 int totalWrong(int n) {    int a=0,b=1; int ans=1;     for(int i=3;i<=n;++i){ ans=(i-1)*(a+b); a=b;b=ans; }     return (n==1)?0:ans; }

n!-c(n,1)*(n-1)!-...-c(n,n)*0!

function f(n){ if(n < 2) return 0; if(n === 2) return 1; return (n - 1)*(f(n-1)+f(n-2)); }

错排，离散还是概率论有讲过来着😂

有个公式，n!*(1/2!-1/3!+1/4!-1/5!+...+(-1)^n*1/n!)

编程之美上面有这道题

错排了解一下

错排。

信封问题   动态规划可解

1/n？，瞎猜的

大佬什么岗？

组合排列中的非对号入座问题，有通项公式的，可以上网查查

n-1的阶乘