爬楼梯

用递归将问题分解为规模更小的子问题进行求解

描述

树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数， 求不同的走法数 例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一 级，第二次走两级，也可以第一次走两级，第二次走一级，一 共3种方法。 输入 输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30输出不同的走法数，每一行输入对应一行 输出 不同的走法数，每一行输入对应一行输出

样例输入

5 8 10

样例输出

8 34 89

分析： n级台阶的走法 = 先走一级后，n-1级台阶的走法 +先走两级后，n-2级台阶的走法 f(n) = f(n-1)+f(n-2) 边界条件： n < 0 0 n = 0 1 n = 1 1 (阻止无穷递归的发生) n = 0 1 n = 1 1 n = 2 2

递归的解法

#include <iostream> using namespace std; int N; int stairs(int n) { if( n < 0) return 0; if( n == 0 ) return 1; return stairs(n-1) + stairs(n-2); } int main() { while(cin >> N) { cout << stairs(N) << endl; } return 0; }

或者这样写 ：先预处理然后再用

#include <iostream> using namespace std; #define N 30 int main() { int f[N]; f[1] = 1; f[2] = 2; for(int i=3; i<=N; i++) f[i] = f[i-1] + f[i-2]; int n; while(cin >> n) cout << f[n] << endl; return 0; } ReCclay 认证博客专家 嵌入式软件开发 机器/深度学习 全栈技术学习者 大家好，我是博主ReCclay，目前处于研究生阶段，就读于电子科技大学，主攻方向为汽车辅助驾驶算法研究。入站以来，凭借坚持与热爱，以博文的方式分享所学，截止目前累计博文数量达800余篇，累计受益人次达130w+次，涉及领域包括但不限于物联网开发、单片机开发、Linux驱动开发、FPGA开发、前/后端软件开发等。在未来我将继续专注于嵌入式相关领域，学习更多的科技知识，输出更高质量的博文。