算法训练 - 第39级台阶
一、引入：
如果我每一步只能迈上1个或2个台阶。
先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。
那么，上完39级台阶，有多少种不同的上法呢？ 二、分析：
一次迈 1个或2个 台阶；
先迈左脚，然后左右交替，最后一步迈右脚，走偶数步 ，上39阶；
递归。
三、代码：
#include<iostream>
using namespace std;
int f(int n,int step){
if(n==0){
if(step%2==1) return 0;
else return 1;
}
if(n==1){
return f(n-1,step+1);
}
if(n==2 ){
return f(n-1,step+1)+f(n-2,step+1);
}
return f(n-1,step+1)+f(n-2,step+1);
}
int main(){
cout<<f(39,0);
return 0;
}
// ans:51167078
