劍指offer-跳台階

跳台階

• 題目描述
• 算法思路
• 代碼實作
• • 遞歸
  • 記憶化搜尋（動态規劃）
  • 優化存儲空間
• 總結

題目描述

一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法（先後次序不同算不同的結果）。

示例1

輸入：2
傳回值：2
           

示例2

輸入：7
傳回值：21
           

算法思路

與斐波那契數列數列一模一樣的思路，可以說完全一樣，請參考這篇文章

斐波那契數列

代碼實作

遞歸

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

記憶化搜尋（動态規劃）

采用備忘錄的形式将遞歸結果存儲起來，也就是記憶化搜尋。然後采用自底向上的形式遞推，也就成了動态規劃問題

public class Solution {
    public int jumpFloor(int target) {
        int[] res = new int[100];
        res[1] = 1;
        res[2] = 2;
        for(int i=3;i<=target;i++){
            res[i] = res[i-1] + res[i-2];
        }
        return res[target];
       
    }
}
           

優化存儲空間

目前結果隻與前兩項有關，是以隻需要存儲前兩項的結果即可。

public class Solution {
    public int jumpFloor(int target) {
        if(target==1){
            return 1;
        }
        if(target==2){
            return 2;
        }
        int sum = 0;
        int one = 1;
        int two = 2;
        for(int i=3;i<=target;i++){
            sum = one + two;
            one = two;
            two = sum;
        }
        return sum;
       
    }
}
           

總結

其實這道題目就是斐波那契數列的變形，隻是題目的描述不再是那麼直白，需要自己去發現。