欢迎关注笔者，你的支持是持续更博的最大动力

目录

问题描述思路代码其他

问题描述

爬楼梯：每次走1级或2级

输入：楼梯的级数 输出：不同的走法数

例 楼梯有3级，可以

每次走1级；第一次走1级，第二次走2级；第一次走2级，第二次走1级

共3种方法。

思路

递归 n级台阶的走法 = 先走一级后，n-1级台阶的走法 + 先走两级后，n-2级台阶的走法

$f(n)=f(n-1)+f(n-2)$

边界条件： n=1 1种走法 n=2 2种走法

或其他边界条件：n=0 和n=1。边界条件是用来防止无限递归，根据递推式来设置。

代码

int stairs(int n){ if (n == 1) //边界条件 return 1; if (n == 2) //边界条件 return 2; return stairs(n-1) + stairs(n-2); //调用自己递归 } int main (){ int n; while (cin>> n) { cout << stairs(n) << endl; } return 0; }

注意：递归由于容易栈溢出，所以只能处理小数目，如果超出30级台阶，就会像下面这样： 解决办法：不用递归，用for loop 把结果存起来。

其他

日常vlog: 点这里去B站～