错排问题是组合数学中的问题之一。考虑一个有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为动态规划解法。
