题解 | #跳台阶#

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

/**
 * 解法一：递归（超时）
 * 思路：满足斐波那契数列公式，最简单的肯定是递归
 * 时间复杂度：O(2^n)，每个递归会调用两个递归，因此会成二的指数级增长
 * 空间复杂度：
 */
 export function jumpFloor(number: number): number {
    if (number <= 1) return 1
    return jumpFloor(number - 1) + jumpFloor(number - 2)
}

/**
 * 解法二：循环（记忆化累加）
 * 思路：n1、n2 记录前面两位的结果，一个循环搞定
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
export function jumpFloor(number: number): number {
    if (number <= 2) return number
    
    let n1 = 1 // 记录 n - 1 的结果
    let n2 = 1 // 记录 n - 2 的结果
    let res = 0

    for (let i = 2; i <= number; i++) {
        res = n1 + n2

        // 记录中间结果
        n2 = n1
        n1 = res
    }

    return res
}

/**
 * 解法三：动态规划
 * 思路：
 * 时间复杂度：O(n)
 * 空间复杂度：
 */
export function jumpFloor(number: number): number {
    const dp = new Array(number + 1)
    dp[1] = 1
    dp[2] = 2
    for (let i = 3; i <= number; i++){
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[number]
}

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview