自顶向下 – 递归
var Fibonacci = function(n)
{
let map = {}
map[0] = 0
map[1] = 1
return helper(n, map)
}
function helper(n, map) {
if (map[n] !== undefined) return map[n]
else {
map[n] = helper(n - 1,map) + helper(n - 2,map)
return map[n]
}
}
自底向上 – 循环
var Fibonacci = function(n)
{
let dp = []
dp[0] = 0
dp[1] = 1
for (let i = 2; i < n + 1; i ++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
}