错排问题 错排列题解（Java 递归方法 动态规划方法）

错排问题是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。
错排问题-维基百科

思路：
设方法f(n)，f(n)为n个元素的错排结果数
当n == 1时，无法完成错排，所以结果为0
当n == 2时，只有一种错排方式，所以结果为1
当n >= 3时考虑：
将元素n放到k位置，有(n - 1)种方法

• 此时考虑元素k
  1 假如元素k放到了n的位置，那么就还剩下(n - 2)个元素，这些元素错排的结果数为f(n - 2)
  2 假如元素k不放到n的位置上，那么就剩下(n - 1)个元素，这里也边包括了元素k，这些元素错排的结果数为f(n - 1)

由此得到递归式：(n - 1) * (f(n - 2) + f(n - 1))

package com.example.demo;

import java.util.HashMap;

public class DSolution {
    public static void main(String[] args) {
        DSolution ds = new DSolution();
        System.out.println(new DSolution().dpCount(7));
        System.out.println(new DSolution().dpCount(6));
        System.out.println(new DSolution().dpCount(5));
    }

    private int dCount(int n) {
        if (n == 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        return (n - 1) * (dCount(n - 1) + dCount(n - 2));
    }

    private int dpCount(int n) {
        HashMap<Integer, Integer> resultMap = new HashMap<>();
        resultMap.put(0, 0);
        resultMap.put(1, 0);
        resultMap.put(2, 1);
        for(int i = 3; i <= n; i++) {
            resultMap.put(i, (i - 1) * (resultMap.get(i - 1) + resultMap.get(i - 2)));
        }
        return resultMap.get(n);
    }
}

其中dCount为递归解法，dpCount为动态规划解法。