探秘剑指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)
版权声明:程序员胖胖胖虎阿 发表于 2025年7月10日 下午1:49。
转载请注明:探秘剑指Offer第8题:跳台之法新寻 | 胖虎的工具箱-编程导航

相关文章

暂无评论

暂无评论...