青蛙跳台階

題目描述

一只青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法。

輸入描述

台階級數 target

輸出描述

多少種跳法

題目分析

假設跳上n階台階時有f(n)種跳法　

要跳上ｎ階只能從ｎ－１階或是ｎ－２階跳上去　

那麼有ｆ（ｎ）＝ｆ（ｎ－１）＋ｆ（ｎ－２）成立，這符合斐波那契數列　

顯然n=1時 f(1)=1，n=2時f(2)=2，n=3時f(3)=f(1)+f(2)=3, 我們得出遞推公式：
　　　　 | 1, (n=1)
f(n) = 　 | 2, (n=2)
　　　　 | f(n-1)+f(n-2) ,(n>2,n為整數)

解法一（遞歸）　　運行時間：444ms 占用內存：629k

public class Solution {
    public int JumpFloor(int target) {
        if(target<=0)  return 0;
        if(target<=2)  return target;
        return JumpFloor(target -1)+JumpFloor(target -2);
    }
}

注意輸入限制，在上一題中說到了遞歸調用效率不高， 不推薦

解法二 （動態規劃） 運行時間：33ms 占用內存：654k

public class Solution {
    public int JumpFloor(int target) {
        if(target<=0)  return 0;
        if(target<=2)  return target;

        int i =1;
        int j =2;
        for(;target>2;target--){
            j+=i;
            i=j-i;
        }
        return j;
    }
}

　　首先，可以明顯看出運行時間只有遞歸的十分之一不到。n=1時 f(1)=1，n=2時f(2)=2直接返回.
　　根據n的大小，從f(１)=i 和 f(２)=j 從頭開始遍歷整個序列，由ｆ（ｎ）＝f(n-1)+f(n-2)　（n>2），依次求得後面的結果，最後求得ｆ（target）並返回。