題目標題: 第39級臺階    小明剛剛看完電影《第39級臺階》，離開電影院的時候，他數了數礼堂前的臺階數，恰好是39級!    站在臺階前，他突然又想著一個問題：    如果我每一步只能邁上1個或2個臺階。先邁左腳，然后左右交替，最后一步是邁右腳，也就是說一共要走偶數步。那么，上完39級臺階，有多少種不同的上法呢？    請你利用計算機的優勢，幫助小明尋找答案。要求提交的是一個整數。注意：不要提交解答過程，或其它的輔助說明文字。

答案 ： 51167078

方法 一 是  簡單dfs 深搜  因為不是步數 要么是1  要么是2

#include<stdio.h>int res;void dfs(int step,int k){	if(k<0)		return;	if(step%2==0&&k==0)	{		res++;		return;	}	for(int i=1;i<=2;i++)  //dfs  深搜 要么是 1 步 要么是兩步 	{		dfs(k-i,step+1); 	}}int main(){	dfs(39,0);	PRintf("%d/n",res);}
方法二 是 回溯     要考慮到 必須是前37臺階才能走兩步  38 后 只能走一步
#include<stdio.h>int sum=0;//記錄為走的步數 int x=0;int y=0;int res=0;void bbs(int num){	if(num==39)	{		if(sum%2==0)			res++;		return;	}	else	{		sum++;num++; //走一步 		bbs(num);//回溯 		sum--;num--;//還原		if(num<=37)//只有在 37 之前才能走兩步 		{			sum++;num+=2;			bbs(num);			sum--;num-=2;		} 	} } int main(){	bbs(0);	printf("%d/n",res);	return 0;}