509-斐波那契.md

509-斐波那契

第一种是常见的递归

这种解法的时间复杂度太高了

const fibonacci = function (n) {
    return fibonacci(n - 1) + fibonacci(n - 2);
}

第二种是通过记录所有计算的结果，这样在下一次的计算的时候，是可以从缓存中拿到结果

时间复杂度是 O(n); 这时候的空间复杂度是 O(n);

const fibonacci = function (n) {
    if (n === 0) {
        return 0;
    }
    
    let dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 1;
    
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

第三种方案是继续压缩空间复杂度****

因为每次都是需要前两次的结果，所以不需要去记录太多的结果，所以只需要增加三个变量就可以了 时间复杂度 O(n) 空间复杂度 O(1)

const fibonacci = function (n) {
    if (n < 2) {
        return n;
    }
    
    let p = 0, q = 0, r = 1;
    for (let i = 2; i <= n; i++) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
}

上面的还可以再优化一版更清晰，阅读性更好的，通过for循环和数组的结构来每次更新值

const fibonacci = function (n) {
    if (n === 0) {
        return 0;
    }
    
    let a1 = 0, a2 = 1;
    for (let i = 1; i < n; i++) {
        [a1, a2] = [a2, a1 + a2];
    }
    
    return a2;
}