题解 | #斐波那契数列#

/**
 * 解法一：递归
 * 时间复杂度 O(2^n)
 */
export function Fibonacci(n: number): number {
     if (n === 0) return 0
     if (n === 1) return 1
    
     return Fibonacci(n - 1) + Fibonacci(n - 2)
}

/**
 * 解法二：循环
 * 时间复杂度 O(n)
 */
export function Fibonacci(n: number): number {
    if (n <= 0) return 0
    if (n === 1) return 1

    let n1 = 1 // 记录 n - 1 的结果
    let n2 = 0 // 记录 n - 2 的结果
    let res = 0

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

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

    return res
}