彻底解决爬楼梯问题

话不多说，我们直接进入正题

首先，举个最经典的爬楼梯问题：

- ####假设你正在爬楼梯,有n级楼梯，每次你只能爬1步或者3步，请问有多少种不同的方法爬到楼顶部？

解决这个问题我们可以用到很多方法来求解，如递归调用，备忘录法，动态规划，以及斐波那契数列的通项公式。方法虽多，但只要抓住爬楼梯问题的本质—斐波那契数列。一切就很好办了。

接下来对题目进行分析

- 只有1个台阶的时候    总共有1种走法
- 只有2个台阶的时候    总共有1种走法
- 只有3个台阶的时候    总共有2种走法
- 只有4个台阶的时候    总共有3种走法
- 只有5个台阶的时候    总共有4种走法
- ......

此时我们发现规律：f(n)=f(n-1)+f(n-3),这个递推公式正符合斐波那契数列
还有一个问题：要是遇到了其他的走楼梯方式又该怎么办呢？一样的我们同样如此分析得到其他的表达式：

- 每次可以上1级，2级.
        -：f(n)=f(n-1)+f(n-2)
- 每次可以上1级，2级，3级.
        -：f(n)=f(n-1)+f(n-2)+f(n-3)
......

有了这个递推公式就好办事了，在这里我只贴出递归法和优化动态规划

递归调用法

#include<iostream> 
using namespace std;
long mod=1000000000+7;
//答案很大时用mod=(1e9+7)输出
//递归函数实现:f(n)=f(n-1)+f(n-3)
long Num(int n){
    //n<4独立赋值
    if(n==1) return 1;
    if(n==2) return 1;
    if(n==3) return 2;
    else return Num(n-1)%mod+Num(n-3)%mod;
}
int main(){
    int n;
    cin>>n;
    cout<<Num(n)<<endl;
    //while(cin>>n)cout<<Num(n)<<endl;
    return 0;
}

动态规划

#include<iostream>
using namespace std;
long mod=1000000000+7;
//答案很大时用mod=(1e9+7)输出
//函数实现:f(n)=f(n-1)+f(n-3)
long Num(int n){
    long add[n+1];
    //n<4单独赋值
    add[1]=1;
    add[2]=1;
    add[3]=2;
    if(n==1) return 1;
    if(n==2) return 1;
    //方法实现
    for(int i=4;i<=n;i++){
        add[i]=add[i-1]%mod+add[i-3]%mod;
    }
    return add[n]%mod;
}
int main(){
    int n;
    cin>>n;
    cout<<Num(n)<<endl;
    //while(cin>>n)cout<<Num(n)<<endl;
    return 0;
}

使用递归调用往往在解决n比较小的时候速度较快，一旦n超过某个范围的数，速度就会很慢。因此n较大时建议使用动态规划