《剑指 Offer （第 2 版）》第 10-1 题：跳台阶（斐波拉契数列、滚动变量）

第 10-1 题：跳台阶（斐波拉契数列、滚动变量）

传送门：AcWing：跳台阶，牛客网 online judge 地址，牛客网 online judge 地址。

输入一个整数 $n$ ，求斐波那契数列的第 $n$ 项。

假定从 $0$ 开始，第 $0$ 项为 $0$ 。( $n \le 39$ )

样例：

输入整数 $n=5$

返回 $5$ 。

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

思路：这题的数据范围很小，我们直接模拟即可。当数据范围很大时，就需要采用其他方式了，可以参考求解斐波那契数列的若干方法。写成动态规划，如果使用递归，一定要加上缓存，否则会重复求解子问题，导致效率低下。

题目背景是斐波拉契数列。
在实现的时候思考如何节约空间，其实使用常数级别的辅助空间就可以了。

时间复杂度：总共需要计算 $n$ 次，所以时间复杂度是 $O(n)$ 。

Python 代码1：用两个变量滚动式往后计算， $a$ 表示第 $n−1$ 项， $b$ 表示第 $n$ 项。则令 $c=a+b$ 表示第 $n+1$ 项，然后让 $a$ 、 $b$ 顺次往后移一位。

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

参考资料：面试官问你斐波那契数列的时候不要高兴得太早。书上斐波拉契数列数列空间更省的写法，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);
        }
    }
}

最后编辑于：2019.05.25 01:20:43