08 跳台阶

题目描述

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

示例：

输入: 1, 输出: 1  (1)
输入: 2, 输出: 2  (1+1, 2)
输入: 3, 输出: 3  (1+1+1, 1+2, 2+1)
输入: 4, 输出: 5  (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)

解题思路

核心思想：递归关系。要跳到第n级台阶，最后一步要么从n-1跳1级，要么从n-2跳2级。

递推公式：

f(0) = 1（一种方式：不跳）
f(1) = 1
f(n) = f(n-1) + f(n-2), n >= 2

这实际上是斐波那契数列的变种，只是初始值不同。

时间复杂度：O(n) 空间复杂度：O(1)

Python 实现

python

def jump_floor(n):
    """
    跳台阶问题

    Args:
        n: 台阶数

    Returns:
        int: 跳法总数
    """
    if n <= 1:
        return 1

    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b

    return b


# 动态规划版本
def jump_floor_dp(n):
    """
    动态规划版本
    """
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


# 测试代码
if __name__ == "__main__":
    for i in range(1, 11):
        print(f"跳{i}级台阶: {jump_floor(i)}种跳法")

# 输出:
# 跳1级台阶: 1种跳法
# 跳2级台阶: 2种跳法
# 跳3级台阶: 3种跳法
# 跳4级台阶: 5种跳法
# 跳5级台阶: 8种跳法
# 跳6级台阶: 13种跳法
# 跳7级台阶: 21种跳法
# 跳8级台阶: 34种跳法
# 跳9级台阶: 55种跳法
# 跳10级台阶: 89种跳法

图解

跳台阶分析:
要跳到第n级，最后一步只有两种选择:
1. 从n-1级跳1级上来 → 前面有f(n-1)种跳法
2. 从n-2级跳2级上来 → 前面有f(n-2)种跳法

因此: f(n) = f(n-1) + f(n-2)

具体例子:
n=1: 1种 (1)
n=2: 2种 (1+1, 2)
n=3: 3种 (1+1+1, 1+2, 2+1)
n=4: 5种
     从第3级跳1级: 1+1+1+1, 1+2+1, 2+1+1 (3种)
     从第2级跳2级: 1+1+2, 2+2 (2种)
     总共: 3+2=5种

08 跳台阶 ​

题目描述 ​

解题思路 ​

Python 实现 ​

图解 ​

08 跳台阶

题目描述

解题思路

Python 实现

图解