动态规划算法

动态规划算法将整个问题分成多个小问题，将所有小问题解决掉，之后合并成一个整体的解决方案。
下面我们举一个例子看一下动态规划算法的实现。

斐波那契数列问题

斐波那契数列 0,1,1,2,3,5,8,13,21...，斐波那契数列是有前两项的值相加而成。

const fib = (n) => {
  const arr = [];
  for(let i = 0;i<n;i++){
     arr[i] = 0
  }

 if(n === 1 || n === 2){
    return 1
  }else{
    arr[1] = 1
    arr[2] = 1
    for(let j = 3; j < n; j++){
      arr[j] = arr[j -1] + arr[j -2]
    }
    return arr[n-1]
  }
}

我们在数组中保存每一步的计算结果，这是与递归不同之处。那么我们看一下递归算法的实现和两者的耗时对比。
递归算法实现斐波那契数列如下

 const fib1 = (n) =>{
     if(n < 2){
       return n
     }else{
         return fib1(n-1) + fib1(n-2)
     }
 }

 const startTime = new Date().getTime()
 fib(1000)
 const stopTime = new Date().getTime()
 console.log(stopTime - startTime) // 0

 const startTime1 = new Date().getTime()
 fib1(1000)
 const stopTime1 = new Date().getTime()
 console.log(stopTime1 - startTime1) // 2

结果看出动态规划算法的耗时较短。

我们也可以在不使用数组的情况下，使用动态规划来保存每一步的执行结果。

 const fib = (n) = >{
  let result = 0
  let prev = 1
  let next =1
  for(let i =2 ;i<n;i++){
    result  = prev + next;
    prev = next;
    next = result
  }
  return result
}