n个人排队都不站在原来的位置

题目描述：有n个人首先站成一排，请问，当n个人第二次再重新排列，每个人都不在原来的位置上，问有多少种站法。例如，原来有3个人，ABC，那么第二次每个人都不在原来的位置上有2种站法，BCA和CAB。

---

解决思路：

• 假设有n个人，那么我们的问题规模是 A(n)，A(n) 代表的是 n 个人都不站原来的位置一共有多少种站法。令第一个人站的是非1号位置，一共是 n-1 种站法，假设第一个人站在2号位置，那么第2个人站的位置分两种：第一类是第2个人站1号位置，那么第1个人和第2个人的位置都确定了，那么剩下 n-2 个位置，问题规模变成 A(n-2)，相当于第3个人不站3号位置，第4个人不站4号位置....第n个人不站 n 号位置；第二类是第2个人不战1号位置，那么问题的规模变成了 A(n-1)，相当于第2个人不站1号位置，第3个人不站3号位置...第 n 个人不站 n 号位置。所以最终得到 。其实代码很简单，就是一个递推的过程，反倒是想不到这么做。

import java.util.*;

public class Main {

    public static int queue(int n){
        if(n <= 1)
            return 0;
        if(n == 2)
            return 1;
        int num_1 = 0, num_2 = 1, num_3 = 0;
        for(int i = 3; i <= n; i++){
            //这里是一个递推的过程
            num_3 = (i - 1) * (num_2 + num_1);
            num_1 = num_2;
            num_2 = num_3;
        }
        return num_3;
    }

    public static int fun(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        int[] arr = new int[n + 1];
        arr[1] = 0;
        arr[2] = 1;
        //用数组表示，只是很方便的显示公式效果
        //有值有下标，可以一一对应。
        for(int i = 3; i <= n; i++) {
            arr[i] = (i - 1) * (arr[i - 1] + arr[i - 2]);
        }
        return arr[n];
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println(queue(n));
    }
}