算法题-骨牌覆盖（java）

思路：可以理解为排列组合和递归的结合，横杠每次只能两个一起出现，并且在同一列。假设n为6。

初始化时 令 num = 1，即全||||||的情况。
如果n为偶数，num++，即全 ===的情况。
递归第一次：=||||，=有C(5,4)种排放方式。
递归第二次：==|| ，=有C(4,2)种排放方式。
递归第三次：n==0，递归条件为n>0，结束递归。

import java.util.Scanner;

public class Oj6 {
	static double num=1;//全||||||的情况
	static int flag1;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int n = sc.nextInt();
			if(n%2==0)
				num++;//全===的情况
			flag1=n-1;//flag1每次-1，虽然=占用两个位置，但=也占用一个位置，所以总的数量为每次-1
			func(n-2);//每次n-2,因为=占用两个位置
			System.out.println((int)num);
			num=1;
		}

	}
	
	static void func(int n) {
		
		if(n>0) {//递归结束条件
				num=num+fc(n,flag1);
				flag1--;
				func(n-2);
		}
	}

//计算排列组合
	private static double fc(int n, int flag2) {
		
		double a=1;
		double b=1;
		int z=0;
		for(int i=flag2;i>=1;i--) {
			a=a*i;
		z++;
		if(z==n)
			break;
		}
		for(int i=n;i>=1;i--)
			b=b*i;
		return a/b;
	}
}