09 变态跳台阶

题目描述

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

示例：

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

解题思路

核心思想：每次跳可以选择1到n级，从n级台阶跳，第一次可以选择跳任意级数。

递推公式：

• f(0) = 1
• f(1) = 1
• f(n) = f(0) + f(1) + ... + f(n-1), n >= 2

简化：

• f(n-1) = f(0) + f(1) + ... + f(n-2)
• f(n) = 2 * f(n-1)

因此答案是 2^(n-1)。

时间复杂度：O(n) 或 O(log n)（使用位运算） 空间复杂度：O(1)

Python 实现

def jump_floor_ii(n):
    """
    变态跳台阶问题

    Args:
        n: 台阶数

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

    # f(n) = 2^(n-1)
    return 2 ** (n - 1)


# 使用位运算优化
def jump_floor_ii_bit(n):
    """
    使用位运算计算 2^(n-1)
    """
    if n <= 0:
        return 1
    return 1 << (n - 1)


# 迭代版本
def jump_floor_ii_iterative(n):
    """
    迭代版本: f(n) = 2 * f(n-1)
    """
    if n <= 0:
        return 1

    result = 1
    for _ in range(1, n):
        result *= 2

    return result


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

# 输出:
# 跳1级台阶: 1种跳法
# 跳2级台阶: 2种跳法
# 跳3级台阶: 4种跳法
# 跳4级台阶: 8种跳法
# 跳5级台阶: 16种跳法
# 跳6级台阶: 32种跳法
# 跳7级台阶: 64种跳法
# 跳8级台阶: 128种跳法
# 跳9级台阶: 256种跳法
# 跳10级台阶: 512种跳法

图解

变态跳台阶分析:
f(n) = f(n-1) + f(n-2) + ... + f(1) + f(0)

因为: f(n-1) = f(n-2) + f(n-3) + ... + f(1) + f(0)

所以: f(n) = 2 * f(n-1)

递推过程:
f(0) = 1
f(1) = 1
f(2) = 2 * f(1) = 2
f(3) = 2 * f(2) = 4
f(4) = 2 * f(3) = 8
...

n=3的所有跳法:
1+1+1, 1+2, 2+1, 3 → 共4种

结论: f(n) = 2^(n-1)