#102 记忆化斐波那契函数(Memoization)


  • 0
    administrators

    斐波那契数列指的是类似于以下的数列:

    1, 1, 2, 3, 5, 8, 13, ....
    

    也就是,第 n 个数由数列的前两个相加而来:f(n) = f(n - 1) + f(n -2)

    请你完成 fibonacci 函数,接受 n 作为参数,可以获取数列中第 n 个数,例如:

    fibonacci(1) // => 1
    fibonacci(2) // => 1
    fibonacci(3) // => 2
    ...
    

    测试程序会从按顺序依次获取斐波那契数列中的数,请注意程序不要超时,也不要添加额外的全局变量。

    本题来源:《JavaScript 语言精髓》


  • 0

    
    const fibonacci = ((memory = {}) => n => {
    	if(n < 2) return n
    	if(memory[n-2] === undefined){
    		memory[n-2] = fibonacci(n-2)
    	}
    	if(memory[n-1] === undefined){
    		memory[n-1] = fibonacci(n-1)
    	}
    	return memory[n] = memory[n-1] + memory[n-2]
    })()
    
    

    快在哪里 计算上来说感觉都要算一遍呀,为啥下面都就超时了

    const fibonacci = n =>{
            let [a, b] = [0, 1]
    	while(n--){[a, b] = [b, a + b]}
    	return a
    }
    

登录后回复
 

与 ScriptOJ 的连接断开,我们正在尝试重连,请耐心等待