509-fibonacci-number

DevGod

Vtuber

Caution

DevGod needs to write an editorial for this problem!

c

int fib(int n){
    if (n <= 1) return n;
    else if(n <= 4){return n-1;}

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

js

/**
 * @param {number} n
 * @return {number}
 */

var memo = {};

var fib = function(n) {
    if(n == 0){return 0;}
    if(n<=2){return 1;}

    if(memo[n] === undefined){
        memo[n] = fib(n-1)+fib(n-2);
    }

    return memo[n];
};

py

class Solution:
    @cache
    def fib(self, n: int) -> int:
        if(n == 0):
            return 0
        if(n == 1):
            return 1
        return self.fib(n-1)+self.fib(n-2)