斐波那契函数与动态规划

传统实现斐波那契函数方法

function fabbi(n){
    if(n==1||n==2){
        return n 
    }
    if(n>2){
        return fabbi(n-2)+fabbi(n-1)
    }
}
fabbi(1)
fabbi(10)

动态规划将递归转成了迭代，避免了大量的重复计算

function fabbi(n){
    let arr = [0,1,1]
    for(let i=3;i<=n;i++){
        arr[i]=arr[i-1]+arr[i-2]
    }
    return arr[n]
}
fabbi(3)