青蛙跳台阶,能写一个复杂度更低的解法吗?

青蛙跳台阶,能写一个复杂度更低的解法吗?插图亿华云

大家好,我是年年!今天的内容是关于一道算法题——青蛙跳台阶。这是一个面试很喜欢考的题,看到它,大部分人脑海中应该立马出现:斐波那契亚数列——递归——f(n)=f(n-1) f(n-2)。

但辅导的小伙伴上周在面试中遇到的问题是:除了递归,能不能写出别的解法,降低算法的时间复杂度。这篇文章给出这道题的更优解。

题目

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

分析

这是一个最基础的动态规划类问题,首先来讲一下思路:当n较小时,可以直接枚举得到结果:

n=1时,青蛙仅有直接跳上一级台阶这种跳法,即一种跳法;n=2时,青蛙可以先跳 上 1 级,然后再跳 上 1 级到达2级台阶,;也可以直接跳 2 级台阶,即一共有两种解法;

当n较大时,去枚举不现实了。但可以想象一下青蛙“最后一跳”有哪些情况:因为青蛙一次可以跳1个或2个台阶,所以只可能是两种情况:从n-1级跳1级上去,以及从n-2阶的位置跳2级上去。我们想要知道跳n级台阶有多少种解法,只需要知道跳n-1级台阶和跳n-2级台阶的跳法,把他们加起来就可以。即得到一个公式f(n)=f(n-1) f(n-2)。

常规解法(递归)

看到这个式子f(n)=f(n-1) f(n-2),应该很快能反应:斐波那契亚数列,代码很容易写出来。递归的关键是确认递归出口,即:当只有1级台阶,只有一种跳法;只有2级台阶时,有两种跳法。

代码如下:

function frogJump(n) {

if (n

THE END
Copyright © 2024 亿华云