用递归将问题分解为规模更小的子问题进行求解
树老师爬楼梯,他可以每次走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开发、前/后端软件开发等。在未来我将继续专注于嵌入式相关领域,学习更多的科技知识,输出更高质量的博文。