大家好，我是念念！今天的内容是一道算法题——青蛙跳步。这是我喜欢在采访中提出的问题。看到它，大多数人应该第一时间想到：斐波那契数列——递归——f(n)=f(n-1)+f(n-2)。但是辅导小伙伴上周面试遇到的问题是：除了递归，能不能写出其他方案来降低算法的时间复杂度。本文针对这个问题给出了更好的解决方案。问题一只青蛙一次可以跳1步或2步。找出青蛙有多少种方式可以跳上n级台阶？分析这是最基本的动态规划问题。先说一下思路：当n较小时，直接枚举得到结果：当n=1时，青蛙只能直接跳到下一步，即A跳法；当n=2时，青蛙可以先跳到level1，再跳到level2到达level2；也可以直接跳到level2，即有两种解法；当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)，应该能很快反应过来：斐波那契数列，代码很容易写出来。递归的关键是确认递归出口，即：当只有一步时，只有一种跳转方式；当只有两步时，有两种跳跃方式。代码如下：functionfrogJump(n){if(n>=3){letresult=frogJump(n-1)+frogJump(n-2)returnresult}elseif(n===1){return1}elseif(n===2){return2}}letresult=frogJump(6)//13console.log(result)复杂度分析上面的递归解只有60个点，因为时间复杂度太高了。可以看出，由于没有保存结果，重复的计算步骤很多：为了得到f(6)的结果，需要计算f(5)和f(4)，为了得到f(5)的结果，需要计算f(4)和f(3)，这里f(4)的两次计算是独立的事件，也就是我们做了大量的重复。将上面的树补成一棵完整的树，如下：该算法的复杂度可以用2^0+2^1+2^2+...+2^4表示，即时间复杂度约为O(2^N)（回想一下高中数学中的几何数列）。空间复杂度是调用栈的深度。从上图可以看出，最大栈深度为n-1，即空间复杂度为O(n)高级解（尾递归）。上述解的时间复杂度很高，因为做了很多次重复计算，从递推公式可以看出：f(n)=f(n-1)+f(n-2)=f(n-2)+f(n-3)+f(n-3)+f(n-4)，一为二，二为四，四为八，整个计算过程好像展开了。每次调用都不保留“状态”，造成大量的计算浪费。只要我们保留计算结果，时间复杂度就可以控制在O(n)，也就是后面的“尾递归”。代码如下：functionfrogJump(first,second,n){leta=first,b=secondletc=first+secondif(n>3){a=secondb=first+secondreturnfrogJump(a,b,n-1)}elseif(n===3){returnc}elseif(n===2){return2}elseif(n===1){return1}}让结果=frogJump(1,2,6)console.log(result)我们使用三个变量abc来保存计算结果，避免重复工作。从first=1，second=2开始计算，每次递归调用都会更新first和second的值，这是每次计算的结果保存下来供下次递归使用。直到n=3，满足递归终止条件。复杂度分析这种尾递归的时间复杂度仅为O(N)，但却是几种解法中最难想到和理解的。空间复杂度是递归的深度，是O(N)。进阶解决方案（循环）循环和递归可以相互转化，所以一个优化思路是用循环来实现上面的逻辑。functionfrogJump(n){if(n===1){return1}elseif(n===2){return2}else{让a=1,b=2,c让count=0while(count
