探秘剑指Offer第8题：跳台之法新寻

探寻剑指Offer第8题：台阶跳跃之策新探

题目

有一只青蛙，一次能跳1级台阶，也能跳2级。现要计算这只青蛙跳上n级台阶的总跳法数，先后次序不同算不同结果。

示例1
输入：2
输出：2
解释：青蛙跳两级台阶有两种方式，先跳一级再跳一级，或者直接跳两级，所以结果是2。

示例2
输入：7
输出：21

示例3：
输入：0
输出：0

思路及解答

动态规划

该题与第7题斐波那契数列问题类似，只是题目表述不同。

青蛙跳到第n级台阶的跳法数dp[i]由两种最后一步情况决定：
- 从第i-1级跳1级上来，跳法数为dp[i-1]
- 从第i-2级跳2级上来，跳法数为dp[i-2]

用数组dp，其中dp[i]表示跳到第i级的跳法数。

状态转移：dp[i] = dp[i-1] + dp[i-2]，初始化dp[1] = 1，dp[2] = 2

public int rectCover(int target) {
    if (target <= 2) {
        return target;
    }

    int[] dp = new int[target + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= target; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[target];
}

• 时间复杂度 O(n)
• 空间复杂度 O(n)

动态规划（滚动数组优化）

观察状态转移方程可知，当前状态仅依赖前两个状态（dp[i-1]和dp[i-2]），因此只需保存这两个值，无需存储整个数组。

public class Solution {
    public int rectCover(int target) {
        if (target <= 0) {
            return 0;
        }
        if (target < 3) {
            return target;
        }
        int num1 = 1; // 代表 dp[i-2]
        int num2 = 2; // 代表 dp[i-1]
        int result = 0;
        for (int i = 3; i <= target; i++) {
            result = num1 + num2;
            //更新前两项
            num1 = num2;
            num2 = result;
        }
        return result;

    }
}

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

如何思考空间优化方法？

1. 观察状态依赖 ： 确认当前状态是否仅依赖有限的前几个状态（如斐波那契数列仅依赖前两项）
2. 变量替换 ： 用固定数量的变量替代数组，滚动更新这些变量
3. 边界处理 ： 初始化时需明确前几个状态的初始值（如 f(1) 和 f(2)）