DP算法（Dynamic PRogramming,俗稱動(dòng)態(tài)規(guī)劃）是最經(jīng)典算法之一.本筆記以耳熟能詳?shù)臄?shù)塔問題為引子,深入討論01背包的解決方法.

　　首先,如下圖所示,要求從頂層走到底層,若每一步只能走到相鄰的結(jié)點(diǎn),則經(jīng)過的結(jié)點(diǎn)的數(shù)字之和最大是多少？

　　這個(gè)問題,對(duì)于任意一個(gè)結(jié)點(diǎn),直接選擇數(shù)字大的子結(jié)點(diǎn)顯然是不行的.以9為例,如果選擇15,當(dāng)前和24>21,但是15的兩個(gè)子結(jié)點(diǎn)太小,24+6+18<21+10+18.由此可見,這樣求出每階段的部分最優(yōu)解并不是全局最優(yōu)解.另外,如果用蠻力算法,每條路徑都遍歷一次,那么層數(shù)為n時(shí),路徑總數(shù)呈指數(shù)級(jí)增長(zhǎng)：

　　顯然這種方法的計(jì)算量太大,也不可取.那么此時(shí)用DP算法是行之有效的.具體思想為：從倒數(shù)第二層開始,一層一層向上遍歷.倒數(shù)第二層第一個(gè)結(jié)點(diǎn)是2,如果路徑經(jīng)過2,那么肯定會(huì)選擇數(shù)值較大左子結(jié)點(diǎn)19. 便用19+2=21代替原先的2. 同理18改為18+10=28,9改為19,5改為21. 這樣倒數(shù)第二層就變成21 28 19 21四個(gè)結(jié)點(diǎn),再將最后一層舍棄.這樣一層層向上,直到第一層,選擇第二層較大的那個(gè)結(jié)點(diǎn)加到9上面去,就得出了全局最優(yōu)解.

　　代碼實(shí)現(xiàn)：如果數(shù)字塔為n層,開辟一個(gè)n*n的二維數(shù)組即可,非常簡(jiǎn)單,此處省略.