楼梯问题之递归

核心算法

    

    递推、回溯。

问题描述

     

爬楼梯问题，每次可以走1步或者2步，爬上n层楼梯的总方法。

（是不是你见过的最短的题目描述了，除了a+b）

解题思路

    

    能进则进，不进则退。（回溯法八字真言）

解题步骤

     

• 输入n

• 设地面为第0层

• 利用递归求解

• 参数每次加1或加2

• 参数等于n，答案加1并返回

• 参数大于n，及时返回

• 直到模拟完所有可能

• 输出答案

递归图解

     

代码解析

#include<cstdio>

int n,ans = 0; //n楼梯总数 ans当前方案数

void dfs(int i) { //当前在第i层楼梯上

    if(i == n){ //走到第n层

       ans++;//方案数加1

       return;//及时返回

    }

    if(i >n) { //超过n层

       return;//及时返回

    }

    dfs(i+1);//走一层

    dfs(i+2);//走两层

    return;

}

int main() {

    scanf('%d',&n);

    dfs(0); //从地面开始走

    printf('%d\n',ans);

    return 0;

}

例题推荐

     

【洛谷 P1255】https://www./problemnew/lists?name=1255

思考

    

1. 如果每次都可以爬1级、2级或3级，你会修改吗？
   

2. 如果是每次可以选择m级呢？（m <= n）

3. 上面给出的例题，按照递归算法只可以通过50%的数据，在下一篇文章里会为大家介绍更为高效的递推算法，你可以独立想出来递推公式吗？