【信息学奥赛一本通】1204：爬楼梯（递归）

解题思路：这道题目类似于斐波那契数列的变型，直接看问题，是一个规模很大的问题，我们需要将大规模问题进行分治，就可以用递归求解。我们用sol（n）代表有n级台阶的时候的方法数是多少。我们很容易的发现递归的边界条件是当n 等于0或者n等于1的时候方法只有一种。我们接下来分析递归的主体求sol（n），因为一次可以走一级或者两级，所以到达第n级台阶有两种方式，一种是从第n-1级台阶再走一级 台阶到达第n级台阶，另一种是从第n-2级台阶一次走2级台阶到达第n级台阶，所以sol（n）就可以分解成sol（n-1）和sol（n-2）的和，也就是走到n-1级台阶的方法数加上走到n-2级台阶的方法数

下面附上ac代码

#include 
using namespace std;
long long sol(int n)
{
    if(n==0||n==1)
        return 1;
    else return sol(n-1)+sol(n-2);
}
int main()
{
    int n;
    while(cin>>n)
    {
        cout<