目录

• 509. 斐波那契数

509. 斐波那契数

普通解

/**
 * 面试千万不能这样写，或者要留后手记住第二种。因为这样写会有重复计算的问题。
 * @param n 
 * @returns 
 */
function fib(n: number): number {
    if (n <= 1) return n;

    return fib(n - 1) + fib(n - 2);
}

更优解

const cache = Object.create(null);
function fib(n: number): number {
    if (n <= 1) return n;

    if (!cache[n]) {
        const num = fib(n - 1) + fib(n - 2);
        cache[n] = num;
    }
    return cache[n]
};