資訊專欄INFORMATION COLUMN
摘要：動態規劃有時被稱為遞歸的相反的技術。動態規劃方案通常使用一個數組來建立一張表，用于存放被分解成眾多子問題的解。今天我們先從我們最熟的斐波那契數列數列開始。斐波那契數列在很多地方都會用上，我是從一個臺階問題發現的，同時知道了動態規劃的解法。
前段時間一直寫了幾個算法題目，發現有個很牛逼的算法，動態規劃，雖然有的解題思路和動態規劃很像，但是當時不知道其中的原理和一些通用性，接下來的幾天，通過一些栗子一點一點揭開動態規劃那神秘的面霜，我也是現學現賣的，如果有那里寫錯的歡迎給我留言指正。
動態規劃有時被稱為遞歸的相反的技術。遞歸是從頂部開始將問題分解，通過解決所有分解小問題的方式，來解決整個問題。而動態規劃這是從底部開始解決問題，將所有小問題解決掉，然后合并成整體的解決方案，從而解決掉整個大問題。遞歸方式雖然很簡潔，但是效率不高，但是不能說遞歸是不好的，本質上是，命令式語言和面向對象的語言對遞歸的實現不夠完善，因為它們沒有將遞歸作為高級編程特性。
動態規劃方案通常使用一個數組來建立一張表，用于存放被分解成眾多子問題的解。當算法執行完畢，最終的解法將會在這個表中找到。
今天我們先從我們最熟的斐波那契數列數列開始。
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
這時候我們可以看到少了創建數組這一步，效率沒變，但是空間復雜度變小了。
斐波那契數列在很多地方都會用上，我是從一個臺階問題發現的，同時知道了動態規劃的解法。有興趣的可以在公眾號中回去“臺階問題”
歡迎關注微信公眾賬號查看最新文章
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/86663.html
摘要：根據該規則，返回第個斐波那契數。尾遞歸函數調用自身，稱為遞歸。一個前端眼中的斐波那契數列解斐波那契數列的實用解法調用棧尾遞歸和手動優化尾調用優化譯我從用寫斐波那契生成器中學到的令人驚訝的件事 斐波那契數列是以下一系列數字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數字 0 和 1 ...
摘要：大名鼎鼎的斐波那契數列，，，，，，，，使用數學歸納法可以看出其規律為。對于斐波那契數列的求解，有自頂向下的記憶化搜索遞歸和自下向上的迭代法，他們都使用了動態規劃的思想。 大名鼎鼎的斐波那契數列：0，1，1，2，3，5，8，13，21...使用數學歸納法可以看出其規律為：f(n) = f(n-1) + f(n-2)。 遞歸 下面首先直接使用遞歸（JavaScript實現）來求解第 n ...
摘要：在上做了一道斐波那契數列求和的題目，做完之后做了一些簡單的優化和用另一種方法實現。動態規劃解決方案斐波那契數列求和除了可以用遞歸的方法解決，還可以用動態規劃的方法解決。 在codewars上做了一道斐波那契數列求和的題目，做完之后做了一些簡單的優化和用另一種方法實現。 題目 function fibonacci(n) { if(n==0 || n == 1) r...
摘要：這是一個簡單的遞歸函數，你可以使用它來生成數列中指定序號的數值這個函數的問題在于它的執行效率非常低有太多值在遞歸調用中被重新計算。 本章內容銜接上一章 數據結構與算法：二分查找 內容提要 兩種基本數據結構： 數組 常見操作: 數組降維、數組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 - 如何將問題分成基線條件和遞歸條件 - 分而治之策略解決棘手問題 ...
摘要：這是一個簡單的遞歸函數，你可以使用它來生成數列中指定序號的數值這個函數的問題在于它的執行效率非常低有太多值在遞歸調用中被重新計算。 本章內容銜接上一章 數據結構與算法：二分查找 內容提要 兩種基本數據結構： 數組 常見操作: 數組降維、數組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 - 如何將問題分成基線條件和遞歸條件 - 分而治之策略解決棘手問題 ...
閱讀 1430·2021-11-15 11:38
閱讀 3582·2021-11-09 09:47
閱讀 1979·2021-09-27 13:36
閱讀 3228·2021-09-22 15:17
閱讀 2564·2021-09-13 10:27
閱讀 2876·2019-08-30 15:44
閱讀 1192·2019-08-27 10:53
閱讀 2719·2019-08-26 14:00
