题解 | 跳台阶

1、解题思路

1. 斐波那契数列关系：青蛙跳到第 n 级台阶的跳法数等于跳到第 n-1 级和第 n-2 级台阶的跳法数之和。这是因为青蛙可以从第 n-1 级跳 1 级上来，或者从第 n-2 级跳 2 级上来。初始条件：f(1) = 1（跳 1 级），f(2) = 2（跳 1+1 或直接跳 2 级）。
2. 迭代法（动态规划）：使用循环和变量存储中间结果，避免重复计算。时间复杂度：O(n)，空间复杂度：O(1)。
3. 矩阵快速幂法：用矩阵快速幂将时间复杂度优化到 O(log n)。适用于对时间复杂度要求更高的场景。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    int jumpFloor(int number) {
        // write code here
        if (number == 1) {
            return 1;
        }
        if (number == 2) {
            return 2;
        }
        int a = 1, b = 2, c;
        for (int i = 3; i <= number; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    public int jumpFloor (int number) {
        // write code here
        if (number == 1) return 1;
        if (number == 2) return 2;
        int a = 1, b = 2, c;
        for (int i = 3; i <= number; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
#
class Solution:
    def jumpFloor(self , number: int) -> int:
        # write code here
        if number == 1:
            return 1
        if number == 2:
            return 2
        a, b = 1, 2
        for _ in range(3, number + 1):
            c = a + b
            a, b = b, c
        return b

3、复杂度分析

1. 初始条件：f(1) = 1，f(2) = 2。
2. 迭代过程：使用三个变量 a、b、c 来存储中间结果。a 和 b 分别代表 f(n-2) 和 f(n-1)。每次迭代更新 a 和 b 的值，最终 b 即为 f(n)。
3. 效率：时间复杂度：O(n)，只需一次循环。空间复杂度：O(1)，只使用了常数个变量。
4. 适用性：适用于 n 较小的情况（n ≤ 40）。如果 n 很大（如 n ≤ 10^18），可以使用矩阵快速幂法进一步优化时间复杂度到 O(log n)。