洛谷【算法1-4】递推与递归

数楼梯

题目描述

楼梯有 $N$ 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

4

样例输出 #1

5

提示

• 对于 60% 的数据，N <= 50；
• 对于 100% 的数据，1 <=N <= 5000。

50分题解：

首先想到递归，当n==1或n==2时已经确定，输入n直接往前推。但发现N的范围为0~50000时，用普通的一维数组就不能解决问题了。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int n;
int solve(int n)
{
    if(n==1)
    {
        return 1;
    }
    else if(n==2) return 2;
    else
    {
        return solve(n-1)+solve(n-2);
    }
}
int main()
{
    cin>>n;
    cout<<solve(n)<<endl;
    return 0;
}