跳臺階演算法（升級版） - 知乎

錕斤拷.css-1cd9gw4{margin-left:.3em;}2021-12-22 07:51:20

題目1：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，並分析演算法的時間複雜度。

分析：這道題最近經常出現，包括MicroStrategy等比較重視演算法的公司都曾先後選用過個這道題作為面試題或者筆試題。

首先我們考慮最簡單的情況。如果只有1級臺階，那顯然只有一種跳法。如果有2級臺階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級；另外一種就是一次跳2級。

現在我們再來討論一般情況。我們把n級臺階時的跳法看成是n的函式，記為f（n）。當n>2時，第一次跳的時候就有兩種不同的選擇：一是第一次只跳1級，此時跳法數目等於後面剩下的n-1級臺階的跳法數目，即為f（n-1）；另外一種選擇是第一次跳2級，此時跳法數目等於後面剩下的n-2級臺階的跳法數目，即為f（n-2）。因此n級臺階時的不同跳法的總數f（n）=f（n-1）+（f-2）。

我們把上面的分析用一個公式總結如下：

分析到這裡，相信很多人都能看出這就是我們熟悉的Fibonacci序列。

題目2：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級......它也可以跳上n級。此時該青蛙跳上一個n級的臺階總共有多少種跳法？

分析：用Fib（n）表示青蛙跳上n階臺階的跳法數，青蛙一次性跳上n階臺階的跳法數1（n階跳），設定Fib（0） = 1；

當n = 1 時， 只有一種跳法，即1階跳：Fib（1） = 1；

當n = 2 時， 有兩種跳的方式，一階跳和二階跳：Fib（2） = Fib（1） + Fib（0） = 2；

當n = 3 時，有三種跳的方式，第一次跳出一階後，後面還有Fib（3-1）中跳法； 第一次跳出二階後，後面還有Fib（3-2）中跳法；第一次跳出三階後，後面還有Fib（3-3）中跳法

Fib（3） = Fib（2） + Fib（1）+Fib（0）=4；

當n = n 時，共有n種跳的方式，第一次跳出一階後，後面還有Fib（n-1）中跳法； 第一次跳出二階後，後面還有Fib（n-2）中跳法……………………。。第一次跳出n階後，後面還有 Fib（n-n）中跳法。

Fib（n） = Fib（n-1）+Fib（n-2）+Fib（n-3）+……。。。。+Fib（n-n）=Fib（0）+Fib（1）+Fib（2）+……。+Fib（n-1）

又因為Fib（n-1）=Fib（0）+Fib（1）+Fib（2）+……。+Fib（n-2）

兩式相減得：Fib（n）-Fib（n-1）=Fib（n-1） =====》 Fib（n） = 2*Fib（n-1） n >= 2

遞迴等式如下：