成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

動(dòng)態(tài)規(guī)劃問題（1）——斐波那契數(shù)列

Eminjannn / 2613人閱讀

摘要：動(dòng)態(tài)規(guī)劃有時(shí)被稱為遞歸的相反的技術(shù)。動(dòng)態(tài)規(guī)劃方案通常使用一個(gè)數(shù)組來建立一張表，用于存放被分解成眾多子問題的解。今天我們先從我們最熟的斐波那契數(shù)列數(shù)列開始。斐波那契數(shù)列在很多地方都會(huì)用上，我是從一個(gè)臺(tái)階問題發(fā)現(xiàn)的，同時(shí)知道了動(dòng)態(tài)規(guī)劃的解法。

前段時(shí)間一直寫了幾個(gè)算法題目，發(fā)現(xiàn)有個(gè)很牛逼的算法，動(dòng)態(tài)規(guī)劃，雖然有的解題思路和動(dòng)態(tài)規(guī)劃很像，但是當(dāng)時(shí)不知道其中的原理和一些通用性，接下來的幾天，通過一些栗子一點(diǎn)一點(diǎn)揭開動(dòng)態(tài)規(guī)劃那神秘的面霜，我也是現(xiàn)學(xué)現(xiàn)賣的，如果有那里寫錯(cuò)的歡迎給我留言指正。

動(dòng)態(tài)規(guī)劃有時(shí)被稱為遞歸的相反的技術(shù)。遞歸是從頂部開始將問題分解，通過解決所有分解小問題的方式，來解決整個(gè)問題。而動(dòng)態(tài)規(guī)劃這是從底部開始解決問題，將所有小問題解決掉，然后合并成整體的解決方案，從而解決掉整個(gè)大問題。遞歸方式雖然很簡(jiǎn)潔，但是效率不高，但是不能說遞歸是不好的，本質(zhì)上是，命令式語(yǔ)言和面向?qū)ο蟮恼Z(yǔ)言對(duì)遞歸的實(shí)現(xiàn)不夠完善，因?yàn)樗鼈儧]有將遞歸作為高級(jí)編程特性。

動(dòng)態(tài)規(guī)劃方案通常使用一個(gè)數(shù)組來建立一張表，用于存放被分解成眾多子問題的解。當(dāng)算法執(zhí)行完畢，最終的解法將會(huì)在這個(gè)表中找到。

今天我們先從我們最熟的斐波那契數(shù)列數(shù)列開始。

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

從數(shù)列中可以發(fā)現(xiàn)從第三個(gè)數(shù)開始的值是前兩個(gè)值的和。

遞歸解法
function fib(n){
    if(n < 2){
        return n;
    }else{
        return fib(n - 1) + fib(n - 2);
    }
}
console.log(fib(10));   // 55
動(dòng)態(tài)規(guī)劃解法
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

從程序中我們可以看出，初始化了一個(gè)和傳入等長(zhǎng)的空數(shù)組，去存放每次運(yùn)算厚的結(jié)果。

測(cè)試程序運(yùn)行時(shí)間
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("動(dòng)態(tài)規(guī)劃消耗" + (stop - start) + "毫秒");

運(yùn)行結(jié)果

55
遞歸消耗-- 0 毫秒
55
動(dòng)態(tài)規(guī)劃消耗-- 0 毫秒

fib(20)

6765
遞歸消耗-- 1 毫秒
6765
動(dòng)態(tài)規(guī)劃消耗-- 0 毫秒

fib(30)

832040
遞歸消耗-- 17 毫秒
832040
動(dòng)態(tài)規(guī)劃消耗-- 0 毫秒

改變fib(n)中的 n 的值我們會(huì)發(fā)現(xiàn)，動(dòng)態(tài)規(guī)劃的解決方案姚比遞歸解決方案高效很多。

優(yōu)化斐波那契數(shù)列的動(dòng)態(tài)規(guī)劃算法

我們看到這個(gè)動(dòng)態(tài)規(guī)劃的算法是要了一個(gè)空數(shù)組，這是你可能已經(jīng)想到使用迭代的方案計(jì)算，可以不使用數(shù)組，需要用到的素組的原因事因?yàn)閯?dòng)態(tài)規(guī)劃算法通常需要吧中間的結(jié)果保存起來。一下是優(yōu)化的迭代版。

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

這時(shí)候我們可以看到少了創(chuàng)建數(shù)組這一步，效率沒變，但是空間復(fù)雜度變小了。

斐波那契數(shù)列在很多地方都會(huì)用上，我是從一個(gè)臺(tái)階問題發(fā)現(xiàn)的，同時(shí)知道了動(dòng)態(tài)規(guī)劃的解法。有興趣的可以在公眾號(hào)中回去“臺(tái)階問題”

歡迎關(guān)注微信公眾賬號(hào)查看最新文章

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/86663.html

相關(guān)文章

  • js 實(shí)現(xiàn)斐波那契數(shù)列(數(shù)組緩存、動(dòng)態(tài)規(guī)劃、尾調(diào)用優(yōu)化)

    摘要：根據(jù)該規(guī)則，返回第個(gè)斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個(gè)前端眼中的斐波那契數(shù)列解斐波那契數(shù)列的實(shí)用解法調(diào)用棧尾遞歸和手動(dòng)優(yōu)化尾調(diào)用優(yōu)化譯我從用寫斐波那契生成器中學(xué)到的令人驚訝的件事 斐波那契數(shù)列是以下一系列數(shù)字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數(shù)字 0 和 1 ...

    趙連江 評(píng)論0 收藏0

  • 從斐波那契數(shù)列看遞歸和動(dòng)態(tài)規(guī)劃

    摘要：大名鼎鼎的斐波那契數(shù)列，，，，，，，，使用數(shù)學(xué)歸納法可以看出其規(guī)律為。對(duì)于斐波那契數(shù)列的求解，有自頂向下的記憶化搜索遞歸和自下向上的迭代法，他們都使用了動(dòng)態(tài)規(guī)劃的思想。 大名鼎鼎的斐波那契數(shù)列：0，1，1，2，3，5，8，13，21...使用數(shù)學(xué)歸納法可以看出其規(guī)律為：f(n) = f(n-1) + f(n-2)。 遞歸 下面首先直接使用遞歸（JavaScript實(shí)現(xiàn)）來求解第 n ...

    charles_paul 評(píng)論0 收藏0

  • 斐波那契數(shù)列求和的js方案以及優(yōu)化

    摘要：在上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡(jiǎn)單的優(yōu)化和用另一種方法實(shí)現(xiàn)。動(dòng)態(tài)規(guī)劃解決方案斐波那契數(shù)列求和除了可以用遞歸的方法解決，還可以用動(dòng)態(tài)規(guī)劃的方法解決。 在codewars上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡(jiǎn)單的優(yōu)化和用另一種方法實(shí)現(xiàn)。 題目 function fibonacci(n) { if(n==0 || n == 1) r...

    xinhaip 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法

    摘要：這是一個(gè)簡(jiǎn)單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號(hào)的數(shù)值這個(gè)函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。 本章內(nèi)容銜接上一章　數(shù)據(jù)結(jié)構(gòu)與算法：二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu)： 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 　　- 如何將問題分成基線條件和遞歸條件 　　- 分而治之策略解決棘手問題 ...

    wuyumin 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法

    摘要：這是一個(gè)簡(jiǎn)單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號(hào)的數(shù)值這個(gè)函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。 本章內(nèi)容銜接上一章　數(shù)據(jù)結(jié)構(gòu)與算法：二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu)： 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 　　- 如何將問題分成基線條件和遞歸條件 　　- 分而治之策略解決棘手問題 ...

    Carson 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<