爬楼梯（递归）

Love The Way You Lie 2022-06-10 13:43 192阅读 0赞

4017:爬楼梯

描述

树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级也可以第一次走两级，第二次走一级，一共3种方法。

输入

输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30

输出

不同的走法数，每一行输入对应一行输出

样例输入

5
    8
    10

样例输出

8
    34
    89

*  [查看][Link 1]
 *  [提交][Link 2]
 *  [统计][Link 3]
 *  [提示][Link 4]
 *  [提问][Link 5]

分析：
    假设f(n)为n个台阶的走法总数，把n个台阶的走法分为两类：

1. 第一步走1阶，剩下还有（n-1）阶要走，有f(n-1)种方法；
    2. 第一步走2阶，剩下还有（n-2）阶要走，有f(n-2)种方法；

因此，f(n)=f(n-1)+f(n-2)
    边界条件：f(1)=1; //只有一阶台阶，只用走一步，一种走法
                   f(2)=2; //有两阶台阶，第一种走法，一次走一步；第二种走法，一次走两步。

#include<iostream>
    using namespace std;
    int f(int n)//爬n级楼梯的走法数
    {
    	if(n==1) return 1;//递归终止条件 
    	if(n==2) return 2;
    	return f(n-1)+f(n-2); 
    } 
    int main()
    {
    	int n;
    	while(cin>>n)
    	{
    		cout<<f(n)<<endl;
    	}
    	return 0;
    }

[Link 1]: http://bailian.openjudge.cn/practice/4017/
[Link 2]: http://bailian.openjudge.cn/practice/4017/submit/
[Link 3]: http://bailian.openjudge.cn/practice/4017/statistics/
[Link 4]: http://bailian.openjudge.cn/practice/hint/4017/
[Link 5]: http://bailian.openjudge.cn/practice/clarify/4017/

发表评论取消回复

表情：

评论列表（有 0 条评论，192人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-分析爬楼梯问题从递归-＞记忆化搜索-＞动态规划

文章目录爬楼梯问题 1.递归思想分析问题代码实现存在的问题 2.记忆化搜索 3.记忆化搜索转化为动态规划爬楼

短命女/ 2023年01月13日 10:47/ 0 赞/ 148 阅读

相关爬楼梯

爬楼梯 1、参考资料 https://leetcode-cn.com/problems/climbing-stairs/ https://segmentfault

╰+哭是因爲堅強的太久メ/ 2022年12月04日 07:36/ 0 赞/ 88 阅读

相关递归（6）：小白上楼梯

题目：小白正在上楼梯，楼梯有 n 阶台阶，小白一次可以上1阶，2阶或者3阶。实现一个方法，计算小白有多少种走完楼梯的方式。代码实现：

旧城等待，/ 2022年12月04日 01:08/ 0 赞/ 97 阅读

相关递归-跳台阶/爬楼梯

70. [爬楼梯][Link 1] 前往楼梯顶部最后一跳要么是1台阶, 要么是两阶, 所以只要把x-1阶的部署加上x-2阶的步数,就能算出x阶的步数了 f(x)=f(x

逃离我推掉我的手/ 2022年10月13日 12:34/ 0 赞/ 139 阅读

相关爬楼梯

如果每次可以上一级台阶或者两级台阶，那么上 n 级台阶一共有多少种方案？ \include<stdio.h> int main() \{ int n; int

冷不防/ 2022年07月14日 09:09/ 0 赞/ 282 阅读

相关递推——爬楼梯

Problem Description 小明是个非常无聊的人，他每天都会思考一些奇怪的问题，比如爬楼梯的时候，他就会想，如果每次可以上一级台阶或者两级台阶，那么上 n 级台

- 日理万妓/ 2022年07月13日 12:29/ 0 赞/ 8 阅读

相关爬楼梯

爬楼梯 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Problem Desc

墨蓝/ 2022年07月12日 12:36/ 0 赞/ 164 阅读

相关爬楼梯（递归）

4017:爬楼梯描述树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级也可

Love The Way You Lie/ 2022年06月10日 13:43/ 0 赞/ 193 阅读

相关爬楼梯

1.知识点：递推 2.题意：如果每次可以上一级台阶或者两级台阶，那么上 n 级台阶一共有多少种方案 3.递推关系方程：a\[i\] = a\[i-1\] + a\[i-

傷城~/ 2022年05月30日 08:47/ 0 赞/ 162 阅读

相关爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：

小鱼儿/ 2022年02月27日 15:44/ 0 赞/ 201 阅读