第 10-1 題：跳臺階（斐波拉契數(shù)列、滾動變量）

傳送門：AcWing：跳臺階，牛客網(wǎng) online judge 地址，?？途W(wǎng) online judge 地址。

輸入一個整數(shù) ，求斐波那契數(shù)列的第 項。

假定從 開始，第 項為 。()

樣例：

輸入整數(shù)

返回 。

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

思路：這題的數(shù)據(jù)范圍很小，我們直接模擬即可。當(dāng)數(shù)據(jù)范圍很大時，就需要采用其他方式了，可以參考求解斐波那契數(shù)列的若干方法。寫成動態(tài)規(guī)劃，如果使用遞歸，一定要加上緩存，否則會重復(fù)求解子問題，導(dǎo)致效率低下。

• 題目背景是斐波拉契數(shù)列。
• 在實現(xiàn)的時候思考如何節(jié)約空間，其實使用常數(shù)級別的輔助空間就可以了。

時間復(fù)雜度：總共需要計算 次，所以時間復(fù)雜度是 。

Python 代碼1：用兩個變量滾動式往后計算， 表示第 項， 表示第 項。則令 表示第 項，然后讓 、 順次往后移一位。

class Solution(object):
    def Fibonacci(self, n):
        """
        :type n: int
        :rtype: int
        """

        if n == 0:
            return 0
        if n == 1:
            return 1
        a = 0
        b = 1

        while n:
            c = a + b
            # “滾動變量”：接下來重新定義 a 和 b
            a = b
            b = c
            n -= 1
        return a

Python 代碼2：Python 語法糖，了解即可

class Solution(object):
    def Fibonacci(self, n):
        """
        :type n: int
        :rtype: int
        """

        if n == 0:
            return 0
        if n == 1:
            return 1
        a = 0
        b = 1

        while n:
            a , b = a + b , a
            n -= 1
        return a

Python 代碼3：

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        a = 0
        b = 1
        
        while n:
            a , b = b , a + b 
            n -= 1
        return b

參考資料：面試官問你斐波那契數(shù)列的時候不要高興得太早。書上斐波拉契數(shù)列數(shù)列空間更省的寫法，P76。

Java 代碼：

public class Solution {

    // 1 1 2 3 5 8
    // 0 1 2 3 4 5
    public int Fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int fibonacci = solution.Fibonacci(5);
        System.out.println(fibonacci);
    }
}

Java 代碼：

public class Solution {

    // 1 2 3 5 8
    // 1 2 3 4 5
    public int JumpFloor(int target) {
        int n = target;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // i j （i+j）
    // 1 2 3 5
    // 1 2 3 4
    public int JumpFloor1(int target) {
        if (target == 1) {
            return 1;
        }
        int n = target;
        int i = 1;
        int j = 2;
        int temp;
        for (int k = 3; k <= n; k++) {
            temp = j;
            j = i + j;
            i = temp;
        }
        return j;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (int i = 1; i < 5; i++) {
            int jumpFloor = solution.JumpFloor1(i);
            System.out.println(jumpFloor);
        }
    }
}