蓝桥杯算法训练VIP-摆动序列-题解（Java代码） 详细代码注释

参考代码:

import java.util.Scanner;


public class zz摆动序列 {

	/**
	 * @param args
	 */
	static int n;
	static boolean []is;//用于记录是否用过（保证每个数都是不相同的）
	static int []cz;//用于保存摆动序列
	static int num=0;//用于记录摆动序列
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		n=scanner.nextInt();
		is=new boolean[n+1];
		cz=new int[n+1];
		dfs(1);
		System.out.println(num-n);

	}
	
	public static void dfs(int k) {
		if (k>n) {
			return;
		}
		//当只有1个和2个数的时候就不用考虑那么多，只要两个数不相等就行了
		if (k==1||k==2) {
			for (int i = 1; i <= n; i++) {
				if (!is[i]) {
					is[i]=true;
					cz[k]=i;
					num++;
					dfs(k+1);
					//回溯
					is[i]=false;
					cz[k]=0;
					
				}
			}
		}
		else {
			//当前一个数比前前一个数大的时候现在的这个数就要比前一个数小
			if (cz[k-1]>cz[k-2]) {
				//这里范围就是1到前一个数（不能等于前一个数）
				for (int i = 1; i < cz[k-2]; i++) {
					if (!is[i]) {
						is[i]=true;
						cz[k]=i;
						num++;
						dfs(k+1);
						//回溯
						is[i]=false;
						cz[k]=0;
					}
				}
			}
			//当前一个数比前前一个数小的时候现在的这个数就要比前一个数大
			else if (cz[k-1]<cz[k-2]) {
				//所以范围是从前一个数（不能等于前一个数）到n
				for (int i = cz[k-2]+1; i <= n; i++) {
					if (!is[i]) {
						is[i]=true;
						cz[k]=i;
						num++;
						dfs(k+1);
						//回溯
						is[i]=false;
						cz[k]=0;
					}
				}
			}
		}
	}

}