前段時(shí)間一直寫了幾個(gè)算法題目梨熙，發(fā)現(xiàn)有個(gè)很牛逼的算法，動(dòng)態(tài)規(guī)劃刀诬，雖然有的解題思路和動(dòng)態(tài)規(guī)劃很像咽扇，但是當(dāng)時(shí)不知道其中的原理和一些通用性，接下來(lái)的幾天，通過(guò)一些栗子一點(diǎn)一點(diǎn)揭開動(dòng)態(tài)規(guī)劃那神秘的面霜质欲，我也是現(xiàn)學(xué)現(xiàn)賣的树埠，如果有那里寫錯(cuò)的歡迎給我留言指正。
動(dòng)態(tài)規(guī)劃有時(shí)被稱為遞歸的相反的技術(shù)嘶伟。遞歸是從頂部開始將問題分解怎憋，通過(guò)解決所有分解小問題的方式，來(lái)解決整個(gè)問題九昧。而動(dòng)態(tài)規(guī)劃這是從底部開始解決問題绊袋，將所有小問題解決掉，然后合并成整體的解決方案耽装，從而解決掉整個(gè)大問題愤炸。遞歸方式雖然很簡(jiǎn)潔，但是效率不高掉奄，但是不能說(shuō)遞歸是不好的规个，本質(zhì)上是，命令式語(yǔ)言和面向?qū)ο蟮恼Z(yǔ)言對(duì)遞歸的實(shí)現(xiàn)不夠完善姓建，因?yàn)樗鼈儧]有將遞歸作為高級(jí)編程特性诞仓。
動(dòng)態(tài)規(guī)劃方案通常使用一個(gè)數(shù)組來(lái)建立一張表，用于存放被分解成眾多子問題的解速兔。當(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é)果保存起來(lái)妓柜。一下是優(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)階問題”
