[LeetCode] Javascript Fib Function 2 Solution

题目

From Bottom To Top

自底向上方式解决fib问题

Runtime: 60 ms, faster than 96.82% of JavaScript online submissions for Fibonacci Number. Memory Usage: 36.7 MB, less than 9.38% of JavaScript online submissions for Fibonacci Number.

var fib = function(N) {
    const map = {
        0:0,
        1:1,
        2:1
    }
    for (let i=3;i<=N;i++) {
        map[i] = map[i-1] + map[i-2]
    }
    return map[N]
}

From Top To Bottom

自顶向下方式解决fib问题

Runtime: 864 ms, faster than 5.10% of JavaScript online submissions for Fibonacci Number. Memory Usage: 44.1 MB, less than 5.47% of JavaScript online submissions for Fibonacci Number.

var fib = function(N) {
    const map = new Map()
    map.set(0,0)
    map.set(1,1)
    
    function run(N) {
        if (map.get(N)!=undefined) {
            return map.get(N)
        }else{
            map.set(N, fib(N-1) + fib(N-2))
            return map.get(N)
        }
    }
    return run(N)
};

dp 思路

上面两种也通常代表了, 动态规划的两种思路:

• 自下而上, 常规思路, 通过化整为零的思路, 逐渐收敛问题,

• 自上而下, 他通常就是利用 dp 以及状态机, 从1 开始, 一直到目标需要求解的 n , 通常有几个状态, 就代表 dp 有几层, 即 dp[状态 1][状态 2], 而上面这个问题, 仅仅只有一个状态就是n, 因此 dp 也仅仅只有一层.

Reference

labuladong - 动态规划解题套路框架