动态规划问题（1）——斐波那契数列

Eminjannn 发布于2019-08-21 11:24 / 2575人阅读

摘要：动态规划有时被称为递归的相反的技术。动态规划方案通常使用一个数组来建立一张表，用于存放被分解成众多子问题的解。今天我们先从我们最熟的斐波那契数列数列开始。斐波那契数列在很多地方都会用上，我是从一个台阶问题发现的，同时知道了动态规划的解法。

前段时间一直写了几个算法题目，发现有个很牛逼的算法，动态规划，虽然有的解题思路和动态规划很像，但是当时不知道其中的原理和一些通用性，接下来的几天，通过一些栗子一点一点揭开动态规划那神秘的面霜，我也是现学现卖的，如果有那里写错的欢迎给我留言指正。

动态规划有时被称为递归的相反的技术。递归是从顶部开始将问题分解，通过解决所有分解小问题的方式，来解决整个问题。而动态规划这是从底部开始解决问题，将所有小问题解决掉，然后合并成整体的解决方案，从而解决掉整个大问题。递归方式虽然很简洁，但是效率不高，但是不能说递归是不好的，本质上是，命令式语言和面向对象的语言对递归的实现不够完善，因为它们没有将递归作为高级编程特性。

动态规划方案通常使用一个数组来建立一张表，用于存放被分解成众多子问题的解。当算法执行完毕，最终的解法将会在这个表中找到。

今天我们先从我们最熟的斐波那契数列数列开始。

0, 1, 1, 2, 3, 5, 8, 13, 21, 24, 55, ...

从数列中可以发现从第三个数开始的值是前两个值的和。

递归解法

function fib(n){
    if(n < 2){
        return n;
    }else{
        return fib(n - 1) + fib(n - 2);
    }
}
console.log(fib(10));   // 55

动态规划解法

function fibDyn(n){
    var temp = [];
    for(var i = 0; i <= n; i++){
        temp[i] = 0
    }
    if(n == 1 || n == 2){
        return 1;
    }else{
        temp[1] = 1;
        temp[2] = 2; 
        for(var i = 3; i < n; i++){
            temp[i] = temp[i - 1] + temp[i -2];
        }
        return temp[i - 1];
    }
}
fibDyn(10)  // 55

从程序中我们可以看出，初始化了一个和传入等长的空数组，去存放每次运算厚的结果。

测试程序运行时间

var start = new Date().getTime();
console.log(fib(10))
var stop = new Date().getTime();
console.log("递归消耗" + (stop - start) + "毫秒");

start = new Date().getTime();
console.log(fibDyn(10))
stop = new Date().getTime();
console.log("动态规划消耗" + (stop - start) + "毫秒");

运行结果

55
递归消耗-- 0 毫秒
55
动态规划消耗-- 0 毫秒

fib(20)

6765
递归消耗-- 1 毫秒
6765
动态规划消耗-- 0 毫秒

fib(30)

832040
递归消耗-- 17 毫秒
832040
动态规划消耗-- 0 毫秒

改变fib(n)中的 n 的值我们会发现，动态规划的解决方案姚比递归解决方案高效很多。

优化斐波那契数列的动态规划算法

我们看到这个动态规划的算法是要了一个空数组，这是你可能已经想到使用迭代的方案计算，可以不使用数组，需要用到的素组的原因事因为动态规划算法通常需要吧中间的结果保存起来。一下是优化的迭代版。

function fibDyn(n){
    var prev = 1;
    var middle = 1;
    var result = 1;

    for(var i = 2; i < n; i++){
        result = prev + middle;
        prev = middle;
        middle = result;
    }
    return result;
}
fibDyn(10)  // 55

这时候我们可以看到少了创建数组这一步，效率没变，但是空间复杂度变小了。

斐波那契数列在很多地方都会用上，我是从一个台阶问题发现的，同时知道了动态规划的解法。有兴趣的可以在公众号中回去“台阶问题”

欢迎关注微信公众账号查看最新文章

云服务器 GPU云服务器波那契数列动态规划动态规划python java动态规划代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/86663.html

js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0
从斐波那契数列看递归和动态规划

摘要：大名鼎鼎的斐波那契数列，，，，，，，，使用数学归纳法可以看出其规律为。对于斐波那契数列的求解，有自顶向下的记忆化搜索递归和自下向上的迭代法，他们都使用了动态规划的思想。大名鼎鼎的斐波那契数列：0，1，1，2，3，5，8，13，21...使用数学归纳法可以看出其规律为：f(n) = f(n-1) + f(n-2)。递归下面首先直接使用递归（JavaScript实现）来求解第 n ...

charles_paul 2019-08-22 18:30 评论0 收藏0
斐波那契数列求和的js方案以及优化

摘要：在上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。动态规划解决方案斐波那契数列求和除了可以用递归的方法解决，还可以用动态规划的方法解决。在codewars上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。题目 function fibonacci(n) { if(n==0 || n == 1) r...

xinhaip 2019-08-20 11:35 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

wuyumin 2019-07-30 15:33 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

Carson 2019-08-26 11:32 评论0 收藏0