相关信息
动态规划背后的基本思想非常简单。就是将一个问题拆分为子问题,一般来说这些子问题都是非常相似的,那么我们可以通过只解决一次每个子问题来达到减少计算量的目的。
一旦得出每个子问题的解,就存储该结果以便下次使用。
斐波那契数列就是从 0 和 1 开始,后面的数都是前两个数之和
0,1,1,2,3,5,8,13,21,34,55,89....
那么显然易见,我们可以通过递归的方式来完成求解斐波那契数列
function fib(n) { if (n < 2 && n >= 0) return n return fib(n - 1) + fib(n - 2) } fib(10)
以上代码已经可以完美的解决问题。但是以上解法却存在很严重的性能问题,当 n 越大的时候,需要的时间是指数增长的,这时候就可以通过动态规划来解决这个问题。
动态规划的本质其实就是两点
根据上面两点,我们的斐波那契数列的动态规划思路也就出来了
function fib(n) { let array = new Array(n + 1).fill(null) array[0] = 0 array[1] = 1 for (let i = 2; i <= n; i++) { array[i] = array[i - 1] + array[i - 2] } return array[n] } fib(10)
本文作者:毛超颖
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!