剑指offer[9]——变态跳台阶
发布日期:2021-05-13 01:00:27 浏览次数:11 分类:博客文章

本文共 460 字,大约阅读时间需要 1 分钟。

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

这个题目是跳台阶的进阶版,其实跟大家分析一下,这道题其实比上一道题简单。在这道题目中,青蛙可以随意一次性跳n级台阶,也就是说如果青蛙想我先枚举一下前几级台阶的跳法数量:

第一级台阶:1=1(直接从平面跳过来)

第二级台阶:1+1=2(从平面跳过来或从第一级跳过来)

第三级台阶:1+2+1=4(从平面跳过来或从第一级或从第二级跳过来)

第四级台阶:1+2+4+1=8

第五级台阶:1+2+4+8+1=16

第六级台阶:1+2+4+8+16+1=32

第七级台阶:1+2+4+8+16+32+1=64

大家观察规律可以看出来下一级台阶的方法数量是前一级台阶的两倍,正好是2的次方:

\[jumpFloorII[n] = 2^{n-1}\]

所以我们就可以很简单的写出算法:

function jumpFloorII(number){    return Math.pow(2, number-1);}
上一篇:剑指offer[10]——矩形覆盖
下一篇:剑指offer[8]——跳台阶

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2025年04月19日 10时15分17秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章