題目：一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳1級(jí)，也可以跳2級(jí)。求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度。

分析：這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過(guò)個(gè)這道題作為面試題或者筆試題。

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

現(xiàn)在我們?cè)賮?lái)討論一般情況。我們把n級(jí)臺(tái)階時(shí)的跳法看成是n的函數(shù)，記為f(n)。當(dāng)n>2時(shí)，第一次跳的時(shí)候就有兩種不同的選擇：一是第一次只跳1級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-1級(jí)臺(tái)階的跳法數(shù)目，即為f(n-1)；另外一種選擇是第一次跳2級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-2級(jí)臺(tái)階的跳法數(shù)目，即為f(n-2)。因此n級(jí)臺(tái)階時(shí)的不同跳法的總數(shù)f(n)=f(n-1)+(f-2)。

我們把上面的分析用一個(gè)公式總結(jié)如下：

        /  1                          n=1
f(n)=      2                          n=2
        \  f(n-1)+(f-2)               n>2

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