[剑指 Offer 第 2 版第 10 题] “跳台阶”做题记录

第 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);
            }
        }
    }