跳台階問題（變态跳台階）

http://blog.csdn.net/hackbuteer1/article/details/6686747

題目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)。

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

          /  1                               n=1

f(n)=      2                              n=2

          \  f(n-1)+(f-2)               n>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

      遞歸等式如下：