leetcode634--错排(我觉得我解释的挺好的,哈哈)

leetcode634--错排(我觉得我解释的挺好的,哈哈)

这个题目是说

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.

There’s originally an array consisting of n integers from 1 to n in ascending order, you need to find the number of derangement it can generate.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:

Input: 3 Output: 2 Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].

Note: n is in the range of [1, 106].

意思就是求一个数组的错排的个数,错排的意思就是自己不要在自己的位置上,这在高中学组合时经常碰到,而且是有递推公式的。这题目可以变着法子问, 比如某次考试,有n个班级,n个老师,要求每个老师不能在自己班监考,问有多少种办法,都是这类题目。

下面来分析一下。

显然 f(0)=0,f(1)=0,f(2)=1, 其中f(n)是当有n个元素的时候的结果,可以这样想,第n个元素放在哪里?假设前面的n-1个已经放好了,第n个元素首先不能放在第n号,那前面n-1个位置就有n-1个选择,假设它就放在1号(这里index从1开始),现在有两种情况。

  • 1放在n号

这时候因为n放在了1号,1放在了n号,所以问题等价于2不能放2号,3不能放3号,…,n-1不能放n-1号,所以是一个子问题,f(n-2),

  • 1不放在n号

这时候因为n放在了1号,所以问题等价于,1不放在n号,2不放在2号,。。。,n-1不放在n-1号,而这和n-1个的子问题是等价的(1不放在n号,和1不放在1号是一个道理),所以是f(n-1),

综上就有递推公式

f(n)=(n-1)(f(n-1)+f(n-2)).

所以f(3)=2,f(4)=9,f(5)=44.

代码如下:

class Solution{
public:
    int find(int n){
        if(n<2) return 0;
        vector<long long> dp(n+1, 0);   //申请n+1个位置,初始化为0.
        
        dp[1] = 0;
        dp[2] = 1;
        for(int i=3;i<n+1;i++){
            dp[i] = (i-1)*(dp[i-1]+dp[i-2]) % (1000000007);
        }
        return dp[n];


    }

};

注意因为数很大,所以题目中要求加上取模运算,因为模运算是满足加法法则的,所以是没有问题的。

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦