剑指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 n
    }
    
    int[] dp = new int[n];
    int dp[1] = 1;
    int 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)）

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top