如果我每一步迈上 1 个或两个台阶，先迈左脚，然后左右交换，最后一步迈右脚，上完 39 级台阶，有多少种不同的方法。

 

思路：因为最后一步迈右脚，所以步数一定是偶数。其次，我们可以不断地递归来完成该算法

 

 

#include<stdio.h>

int total = 0;

int Sum(int num,int step)

{

if(num < 0)

return 0;

if(num == 0 && step%2 == 0)

{

total ++;

return 0;

}

Sum(num-1,step++);

Sum(num-2,step++);

}

int main()

{

int n;

printf("Enter n:");

scanf("%d",&n);

Sum(n,0);

printf("%d",total);

return 0;

}