算法-递归：n级台阶走法问题

算法-递归：n级台阶走法问题 算法-递归 n级台阶，每一次只能选择迈一步或者迈两步，共有多少种走法

#include 
using namespace std;
//n级台阶，每一次只能选择迈一步或者迈两步，共有多少种走法

//方法一：采用递归，时间复杂度为n^2，对于第n级台阶来说，要么是走一步上来的，要么是走两步上来的
int step(int n){
    if(0 >= n){
        return 0;
    }else if(1 == n){
        return 1;
    }else if(2 == n){
        return 2;
    }else{ // n >= 3
        return step(n-1)+step(n-2);
    }
}

int main(){
    int n;
    while(cin>>n){
        cout << "走法为："< 
#include 
using namespace std;
//n级台阶，每一次只能选择迈一步或者迈两步，共有多少种走法

//方法二：采用递归，时间复杂度为n，将n-2的值提前计算出来，只递归n-1
//0:first
//1:second
//2:first+second
//3:second+(first+second)
int step(int first,int second,int n){
    if(0 >= n){
        return 0;
    }else if(1 == n){
        return 1;
    }else if(2 == n){
        return 2;
    }else if (3 == n){
        return first+second;
    }else{ // n > 3
        return step(second,first+second,n-1);
    }
}

int main(){    
    int n;
    while(cin>>n){
        cout << "走法为："<
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5713420.html