题解 | #小乐乐走台阶#

//思路分析：
//小乐乐上课需要走n阶台阶，因为他腿比较长，所以每次可以选择走一阶或者走两阶。
//那么当他走到n阶台阶时，他上一次有两个选择，从n-1阶走过来或者从n-2阶走过来，而n-1阶又可以拆分为(n-1)-1或者（n-1）-2，而(n-2)阶也可以拆分为(n-2)-1或者(n-2)-2，就这样一直拆分下去，直至不可以拆分，也就是1和2。可能有小伙伴好奇为什么没有3或者4，很简单是因为3或者4都还可以继续拆分：3可以拆分为1或者2，而2拆分之后就是1和0，而0阶没有意义。因此我们停止递归的条件就是n<=2(n==1 || n==2)，现在我们就来分析n==1时的走法，很明显只有一种就是1；n==2，有两种走法：一种是走两次1步，还有一种是走一次1步。综上所述：n==1 ——> 1;n==2 ——> 2
//递归的思想：大事化小——>n->n-1和n-2.......1 2

#include <stdio.h>
int fib(int n)
{
    if(n<=2)
    {
        return n;//由上述可推得
    }
    //也可以写成下面这样
    //if(n==1)
    //{
    //    return 1;
    //}
    //if(n==2)
    //{
    //    return 2;
    //}
    return fib(n-1)+fib(n-2);//求n阶的走法，分为两种 n-1 和 n-2
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", fib(n));
    return 0;
}