题解 | 小乐乐走台阶

#include <stdio.h>

int step(int n)
{
    int num = 0;
    if(n == 1)
    {
        num = 1;
    }
    else if(n == 2)
    {
        num = 2;
    }
    else
    {
        num = step(n - 1) + step(n - 2);
    }
    return num;
}

int main() {
    int n = 0;
    scanf("%d", &n);
    int num = step(n);
    printf("%d", num);
    return 0;
}

假设走n步台阶时，有f(n)种解法。因为走台阶的方式有两种，一种是一次走一阶，另一种是一次走两阶。所以有两种情况，一种是第一次是一次走一阶的情况，那么还剩下n-1阶，所以这种情况就有f(n-1)种走法。同理第一步一次走两阶的情况就有f(n-2)种解法。

所以f(n)=f(n-1)+f(n-2)