题解 | 跳台阶

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param number int整型 
 * @return int整型
 */

// // 记忆化搜索：缓存数组，大小为41（覆盖n=1~40的情况）
// int cache[41] = {0};

int jumpFloor(int number ) {
    // // 递归，时间复杂度为O(2^n)，空间复杂度O(n)
    // if (number == 1) {
    //     return 1;
    // } else if (number == 2){
    //     return 2;
    // } else {
    //     return jumpFloor(number-1) + jumpFloor(number-2);
    // }



    // // 记忆化搜索，时间复杂度为O(n)，空间复杂度O(n)
    // // 递归的优化版本，通过 缓存中间结果 避免重复计算
    // // 使用数组存储已计算的 f(n) 值
    // // 递归前检查缓存，缓存未命中时计算并存储
    // // 检查缓存是否命中
    // if (cache[number] != 0) {
    //     return cache[number];
    // }
    // // 基础情况
    // if (number == 1) {
    //     return cache[1] = 1;
    // }
    // if (number == 2) {
    //     return cache[2] = 2;
    // }
    // // 计算并缓存结果
    // return cache[number] = jumpFloor(number - 1) + jumpFloor(number - 2);
    
    
    
    // 动态规划，时间复杂度为O(n)，空间复杂度O(1)
    // 自底向上计算，避免重复计算
    // 使用两个变量保存前两个状态 f(n−1) 和 f(n−2)，无需额外数组
    // 从 n = 3 开始迭代计算，直到 n
    if (number == 1) {
        return 1;
    } else if (number == 2) {
        return 2;
    }

    int a = 1; // f(n-2)，初始为 f(1)
    int b = 2; // f(n-1)，初始为 f(2)
    int combination; // f(n)

    for (int i=3; i<=number; i++) {
        combination = a + b; // 计算 f(n)
        a = b; // 更新 f(n-2) 为 f(n-1)
        b = combination; // 更新 f(n-1) 为 f(n)
    }

    return combination;
}