一本通————1204爬楼梯

1001-高同学

发表文章数:265

热门标签

首页 » LeetCode » 正文

1204:爬楼梯

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 9065     通过数: 4745

【题目描述】

树老师爬楼梯,他可以每次走1级或者2级,输入楼梯的级数,求不同的走法数。

例如:楼梯一共有3级,他可以每次都走一级,或者第一次走一级,第二次走两级,也可以第一次走两级,第二次走一级,一共3种方法。

【输入】

输入包含若干行,每行包含一个正整数N,代表楼梯级数,1≤N≤30。

【输出】

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

【输入样例】

5
8
10

【输出样例】

8
34
89

【来源】

No

 

因为这道题要求方法数目,所以关于这种题目虽然放在递归里面,但可以借助动归的思想。

第一步:确定状态

    考虑最后一个状态,如果要走到第n阶台阶,那么前一步所在的台阶就是(n-ak)。

    这样,就有一个子状态:到第(n-ak)个台阶有几种方式?

    这样,我们就可以写出状态了,即f(n)=m,表示到第n阶台阶有m种方式

 

第二步:状态转移方程

    接下来考虑ak,ak=1或者ak=2。我们分开来看:如果ak=1的话,那么到第n阶台阶有f(n-1)种;如果ak=2的话,那么到第n阶台阶就有f(n-2)种方式。所以,到第n阶台阶,就有f(n-1)+f(n-2)种方式。

 第三步:边界条件

    f(1)=1,f(2)=2。这个条件是题中所给出的。

第四步:确定运算顺序

    大部分情况下都是从小到大进行计算

 

方法一:递归

由于数据规模小,所以可以放心大胆的用递归。递归时间复杂度:O(2^n)

#include <bits/stdc++.h>
using namespace std;

long long f(int n)
{
    if(n==1)
        return 1;
    if(n==2)
        return 2;
    return f(n-1)+f(n-2);
}

int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        cout<<f(n)<<endl;
    }
    return 0;
}

 

方法二:动态规划(时间复杂度O(1))

#include <bits/stdc++.h>
#define MAXN 25535
using namespace std;
int f[MAXN];


int main()
{
    f[1]=1,f[2]=2;
    for(int i=3; i<MAXN; i++)
        f[i]=f[i-1]+f[i-2];
    int n;
    while(scanf("%d",&n)==1)
    {
        cout<<f[n]<<endl;
    }
    return 0;
}

 

标签:

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《一本通————1204爬楼梯》 发布于2020-02-10

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录