動(dòng)態(tài)規(guī)劃
參考鏈接
漫畫(huà)算法奄毡，什么是動(dòng)態(tài)規(guī)劃？
DP
動(dòng)態(tài)規(guī)劃是一種分階段求解決策問(wèn)題的數(shù)學(xué)思想
題目一
問(wèn)：下樓梯問(wèn)題贝或，有一座高度是10級(jí)臺(tái)階的樓梯吼过，從下往上走，每跨一步只能向上1級(jí)或者2級(jí)臺(tái)階咪奖，請(qǐng)問(wèn)有多少中走法盗忱。
思路
剛才這個(gè)題目，你每走一步就有兩種走法羊赵，暫時(shí)不管0級(jí)到8級(jí)臺(tái)階的過(guò)程趟佃。想要走到10級(jí)，必然是從8級(jí)或者9級(jí)走的。那么問(wèn)題來(lái)了闲昭，如果我們以及0到9級(jí)臺(tái)階的走法有x種罐寨，0到8級(jí)臺(tái)階有Y種，那0到10級(jí)臺(tái)階就是X+Y序矩。
公式就是：
F（10） = F（9）+ F（8）
當(dāng)只有1級(jí)臺(tái)階的時(shí)候只有一種解法鸯绿，2級(jí)臺(tái)階的時(shí)候有兩種方法。
遞推公式就是：
F（1） = 1
F（2） = 2
F（N） = F（N-1）+ F（N-2）
動(dòng)態(tài)規(guī)劃的三個(gè)概念：
- 最優(yōu)子結(jié)構(gòu)
- 邊界
- 狀態(tài)轉(zhuǎn)移公式
當(dāng)只有1級(jí)臺(tái)階或2級(jí)臺(tái)階簸淀，我們直接得出結(jié)果楞慈，無(wú)需建華，我們就成F（1）F（2）為邊界啃擦。
F（N） = F（N-1）+ F（N-2）是階段與階段之間的狀態(tài)轉(zhuǎn)移公式。
求解問(wèn)題
方法一：遞歸法
但是復(fù)雜度很高饿悬，因?yàn)楫?dāng)中有很多大量的重復(fù)計(jì)算令蛉。復(fù)雜度
遇到這種情況珠叔，我們只需要?jiǎng)?chuàng)建一個(gè)哈希表，在python種建立一個(gè)字典就好了弟劲。把每次不同參數(shù)的計(jì)算結(jié)果存入哈希祷安，當(dāng)遇到相同參數(shù)時(shí)，再?gòu)墓１砝锩嫒〕鐾闷颍筒粫?huì)重復(fù)計(jì)算了汇鞭。
方法二
感覺(jué)紅色箭頭少了個(gè)參數(shù)。
在以上代碼中庸追，集合map是一個(gè)備忘錄霍骄。當(dāng)每次需要計(jì)算F(N)的時(shí)候，會(huì)首先從map中尋找匹配元素淡溯。如果map中存在读整，就直接返回結(jié)果，如果map中不存在咱娶，就計(jì)算出結(jié)果米间，存入備忘錄中
題目二
國(guó)王和金礦
問(wèn)：有一個(gè)國(guó)家發(fā)現(xiàn)了5座金礦另玖，每座金礦的黃金儲(chǔ)量不同，需要參與挖掘的工人數(shù)也不同。參與挖礦工人的總數(shù)是10人谦去。每座金礦要么全挖慷丽，要么不挖，不能派出一半人挖取一半金礦鳄哭。要求用程序求解出要糊，要想得到盡可能多的黃金，應(yīng)該選擇挖取哪幾座金礦妆丘？
解答
最優(yōu)子結(jié)構(gòu)：
10個(gè)人4金礦（第五金礦不挖的時(shí)候）锄俄，10減去挖第五金礦的人數(shù)要求然后剩下4金礦（第五金礦挖的時(shí)候）。
最終問(wèn)題：
10個(gè)人5金礦的最優(yōu)選擇勺拣。
最優(yōu)子結(jié)構(gòu)和最終問(wèn)題的關(guān)系：
設(shè)幾個(gè)變量便于描述：
N：金礦數(shù)量
W：工人人數(shù)
G[]：金礦黃金含量
P[]：金礦的用工量
關(guān)系：
F（5奶赠，10） = Max（F（4，10）药有，F(xiàn)（4毅戈，10-P[4]）+ G [4]）
==> F（N，W） = Max（F（N-1愤惰，W）苇经，F(xiàn)（N-1，W-P[N-1]）+G[N-1]）
邊界條件：
if N == 1:
if W>= P[0]:
return G[0]
else:
return 0
總結(jié)：
和之前一樣宦言，有三種實(shí)現(xiàn)方式扇单，簡(jiǎn)單遞歸，備忘錄算法奠旺，動(dòng)態(tài)規(guī)劃蜘澜。
方法二：簡(jiǎn)單遞歸
把狀態(tài)轉(zhuǎn)移方程式翻譯成遞歸程序，遞歸的結(jié)束的條件就是方程式當(dāng)中的邊界凉倚。因?yàn)槊總€(gè)狀態(tài)有兩個(gè)最優(yōu)子結(jié)構(gòu)兼都，所以遞歸的執(zhí)行流程類似于一顆高度為N的二叉樹(shù)。方法的時(shí)間復(fù)雜度是稽寒。
方法三：備忘錄算法
在簡(jiǎn)單遞歸的基礎(chǔ)上增加一個(gè)HashMap備忘錄扮碧，用來(lái)存儲(chǔ)中間結(jié)果。HashMap的Key是一個(gè)包含金礦數(shù)N和工人數(shù)W的對(duì)象杏糙，Value是最優(yōu)選擇獲得的黃金數(shù)慎王。方法的時(shí)間復(fù)雜度和空間復(fù)雜度相同，都等同于備忘錄中不同Key的數(shù)量宏侍。
方法四：動(dòng)態(tài)規(guī)劃
規(guī)律
However 赖淤，當(dāng)總工人數(shù)變成1000人，每個(gè)金礦的用工數(shù)也相應(yīng)增加谅河，這時(shí)候如何實(shí)現(xiàn)最優(yōu)選擇呢咱旱？
可能你覺(jué)得還是之前的動(dòng)態(tài)規(guī)劃方法确丢。其實(shí)是不對(duì)的，我們可以來(lái)計(jì)算一下吐限，
1000工人5個(gè)金礦鲜侥，需要計(jì)算1000 * 5 次，需要開(kāi)辟 1000 單位的空間诸典。
然而我們用之前的簡(jiǎn)單遞歸描函，需要計(jì)算2^n次也就是32次，只需要開(kāi)辟5單位（遞歸深度的空間）狐粱。
所以從上面計(jì)算可以知道舀寓，動(dòng)態(tài)規(guī)劃方法的時(shí)間和空間都和W成正比，而簡(jiǎn)單遞歸卻與W無(wú)關(guān)肌蜻，當(dāng)工人數(shù)量很多的時(shí)候互墓，動(dòng)態(tài)規(guī)劃反而不如遞歸。
（我又一個(gè)想法蒋搜，思路來(lái)源于Glibc 中的 qsort() 的實(shí)現(xiàn)在這個(gè)鏈接的舉例分析排序函數(shù)板塊中轰豆，我的思路是這樣的，兩個(gè)算法都可以寫(xiě)在函數(shù)實(shí)現(xiàn)上齿诞，如果當(dāng)N特別大的時(shí)候，可以選擇動(dòng)態(tài)規(guī)劃的方法骂租，而當(dāng)N不大祷杈，而W特別大的時(shí)候，且空間有限制渗饮，此時(shí)就可以讓算法退化成簡(jiǎn)單遞歸但汞。不知道對(duì)不對(duì)這個(gè)思路，如果哪里考慮的不對(duì)的話互站，請(qǐng)告訴我私蕾，萬(wàn)分感謝）
以上就是漫畫(huà)算法的全部?jī)?nèi)容。以下是我的補(bǔ)充內(nèi)容
背包問(wèn)題 和迪杰特斯拉（Dijkstra算法--求圖最短路徑）
背包問(wèn)題
如果認(rèn)真讀了上面的過(guò)程胡桃，看到這個(gè)題目是不是覺(jué)得和前面礦工和金礦很像是不是踩叭。背包問(wèn)題就是，錢(qián)和重量翠胰，而前面礦工和金礦問(wèn)題是容贝，錢(qián)和人數(shù)的限制。
接下來(lái)的思路是算法圖解中關(guān)于動(dòng)態(tài)規(guī)劃的講解之景，可以參考看一下斤富。
寫(xiě)出正確的動(dòng)態(tài)規(guī)劃
Dijkstra's Algorithm（是求從一點(diǎn)出發(fā)的最短路徑）
偽代碼
Data: G, s, dist[], pred[] and
vSet: set of vertices whose shortest path from s is unknown
Algorithm:
dist[] // array of cost of shortest path from s
pred[] // array of predecessor in shortest path from s
dijkstraSSSP(G,source):
| Input graph G, source node
|
| initialise dist[] to all ∞, except dist[source]=0
| initialise pred[] to all -1
| vSet=all vertices of G
| while vSet is not NULL do
| | find s in vSet with minimum dist[s]
| | for each (s,t,w) in edges(G) do
| | relax along (s,t,w)
| | end for
| | vSet=vSet \ {s}
| end while
以上偽代碼僅供參考作用，喜歡的話锻狗，可以研究一下满力。下面通過(guò)一道題目來(lái)了解整個(gè)過(guò)程焕参。
-
根據(jù)偽代碼進(jìn)行初始化：
image - 根據(jù)題目的要求，從node 0開(kāi)始油额，遍歷與0相連的每條邊的權(quán)重叠纷，更新列表，pred代表是從哪里來(lái)的悔耘，比如讲岁，第二列的0，代表從0來(lái)到1衬以。（圖中綠色的代表當(dāng)前遍歷的點(diǎn)）
image -
然后遍歷dist中除去0以外的缓艳，最小的值，以這個(gè)最小值作為起始點(diǎn)看峻，遍歷它連的邊阶淘，更新列表。
image -
其實(shí)就是重復(fù)3的動(dòng)作互妓，先找剩下的最小邊溪窒，遍歷它連的邊，更新列表冯勉，你可以動(dòng)手寫(xiě)一下剩下的內(nèi)容澈蚌。當(dāng)dist發(fā)生變化時(shí)，pred也要相應(yīng)的發(fā)生變化灼狰，畢竟你要記錄最短路徑宛瞄，當(dāng)然要記錄這個(gè)路徑是從哪里來(lái)的。
image
算法復(fù)雜度分析
每條邊都需要遍歷一邊交胚，O（E）
外循環(huán)是遍歷所有點(diǎn)份汗，則是O（V）
"find s in vSet with minimum dist[s]" 這段代碼
嘗試找s in vSet，cost為O（V）
==>overall cost 為
如果用優(yōu)先隊(duì)列來(lái)實(shí)現(xiàn)找最小距離蝴簇，那么
Overall cost =
