前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >上N阶楼梯,一次走1个台阶或者2个台阶,共有多少种走法?

上N阶楼梯,一次走1个台阶或者2个台阶,共有多少种走法?

作者头像
一个架构师
发布2022-06-20 19:40:33
4.5K1
发布2022-06-20 19:40:33
举报
文章被收录于专栏:从码农的全世界路过

假设你需要走n 阶楼梯才能到达楼顶,走楼梯的方式有两种,一次走1个台阶或者一次走2个台阶,问有多少种不同的方法可以走完这n阶楼梯?

先穷举几个n值分析下:

n=1,共1种;

{1}

n=2,共2种;

{1,1},{2}

n=3,共3种

{1,2},

{1,1,1},{2,1}

n=4,共5种

{1,1,2},{2,2},

{1,2,1},{1,1,1,1},{2,1,1}

n=5,共8种

{1,2,2},{1,1,1,2},{2,1,2},

{1,1,2,1},{2,2,1},{1,2,1,1},{1,1,1,1,1},{2,1,1,1}

可以看到,除了n=1和n=2两种情况,是固定的走法外;

走n阶台阶时,可以在n-2个台阶的基础上一次走2个台阶,也可以在n-1个台阶的基础上走1个台阶;也就是f(n)=f(n-1)+f(n-2),这个公式就是著名的斐波那契数列,也叫黄金分割数列、兔子数列.

附上代码:

代码语言:javascript
复制
int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

这段代码虽然很好的表达出了斐波那契数列的含义,却不是算法上最优的.明显在计算n时,会计算两次n-2,时间复杂度是O(n^n),效率相当低的算法了.

稍稍优化下,既然在计算f(n-1)时,已经计算了f(n-2),那只要将计算值记录下来,加运算的f(n-2)部分也就不需要二次计算了;

再优化下,在计算f(n)时需要先计算出来f(n-1),这样就需要压栈,这在空间复杂度上也不是最优,既然需要先计算出f(n-1),才能计算出f(n),那按此思路实现下,先计算f(n-1),再计算f(n).

附上代码:

代码语言:javascript
复制
 long climbStairs2(long n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        long n2 = 1;//n-2
        long n1 = 2;//n-1
        long nn = 0;
        for (int i = 3; i <= n; i++) {
            nn = n1 + n2;
            n2 = n1;
            n1 = nn;
        }
        return nn;
    }

总结下,这个实现方式,时间复杂度为O(n),是非常高效的实现方式.

斐波那契数列

下面回到数列本身,之所以斐波那契数列叫做兔子数列,是因为当时提出来的一个兔子假设.

一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死,那么一年以后可以繁殖多少对兔子?

简单分析下:

容易得出如下结论:

f(1) =1

f(2)=1

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

在看一下称为黄金分割数列的原因,随着n趋向于无穷大,f(n)/f(n+1)的值越趋近于0.618.

看,你又学会了一种算法!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 从码农的全世界路过 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档