* 问题描述:n个人每个人都有自己的位置，问每个人都不坐自己的位置有几种情况
* 思路很简单:递归
* 第一个人可以做其他n-1个位置，当第一个人做每一个位置，比如说第一个人坐2号位置和3号位置的情况是一样多的。
* 然后当第一个人坐2号位置，剩下的情况和原问题并不等价
* 因为原问题每个人都有自己的位置，但是现在子问题2号没有自己的位置，只有多了一个1号位置
* 我们暂时把1号位置认为就是2号自己的位置，不能做的，那么子问题和原问题一样了，子问题是f(n-1)
* 但是事实上2号是可以坐1号位置的，所以我们要再添加一种情况，就是2号坐在1号位置上的情况，
* 它是一个更小的子问题，就是f(n-2)
package DynamicAndRecursive;
public class NN {
/**
* 问题描述:n个人每个人都有自己的位置，问每个人都不坐自己的位置有几种情况
* 思路很简单:递归
* 第一个人可以做其他n-1个位置，当第一个人做每一个位置，比如说第一个人坐2号位置和3号位置的情况是一样多的。
* 然后当第一个人坐2号位置，剩下的情况和原问题并不等价
* 因为原问题每个人都有自己的位置，但是现在子问题2号没有自己的位置，只有多了一个1号位置
* 我们暂时把1号位置认为就是2号自己的位置，不能做的，那么子问题和原问题一样了，子问题是f(n-1)
* 但是事实上2号是可以坐1号位置的，所以我们要再添加一种情况，就是2号坐在1号位置上的情况，
* 它是一个更小的子问题，就是f(n-2)
*/
public static int nn(int n){
if(n == 1){
return 0;
};
if(n == 2){
return 1;
}
return (nn(n - 1) + nn(n - 2)) * (n - 1);
}
public static void main(String[] args){
System.out.print(nn(4));
}
}
