Description 在講述DP算法的時(shí)候，一個(gè)經(jīng)典的例子就是數(shù)塔問題，它是這樣描述的：

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

已經(jīng)告訴你了，這是個(gè)DP的題目，你能AC嗎? Input 輸入數(shù)據(jù)首先包括一個(gè)整數(shù)C,表示測(cè)試實(shí)例的個(gè)數(shù)，每個(gè)測(cè)試實(shí)例的第一行是一個(gè)整數(shù)N(1 <= N <= 100)，表示數(shù)塔的高度，接下來用N行數(shù)字表示數(shù)塔，其中第i行有個(gè)i個(gè)整數(shù)，且所有的整數(shù)均在區(qū)間0,990,99內(nèi)。 Output 對(duì)于每個(gè)測(cè)試實(shí)例，輸出可能得到的最大和，每個(gè)實(shí)例的輸出占一行。 Sample Input 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30 問題分析 本問題采用動(dòng)態(tài)規(guī)劃（DP）解決。 動(dòng)態(tài)規(guī)劃和貪心算法不同，貪心算法通過找到每一個(gè)狀態(tài)最優(yōu)解的情況從而找到整個(gè)問題最優(yōu)解。而有些問題當(dāng)前的最優(yōu)解并不能代表最后的最優(yōu)解，他們最優(yōu)解的情況會(huì)不斷變化。這時(shí)就需要采用動(dòng)態(tài)規(guī)劃思想，不停地跟新當(dāng)前的最優(yōu)狀態(tài)，直到最后達(dá)到最優(yōu)解。 解決動(dòng)態(tài)規(guī)劃的問題關(guān)鍵便是如何正確的轉(zhuǎn)移當(dāng)前的狀態(tài)到下一個(gè)狀態(tài)，也可以理解為將大問題不斷的轉(zhuǎn)化為小問題解決。 比如這個(gè)問題，我們可以通過將第最后一層的葉子結(jié)點(diǎn)加到他的父親節(jié)點(diǎn)上，每個(gè)父親節(jié)點(diǎn)有兩個(gè)孩子節(jié)點(diǎn)，取最大值。這樣第最后一層的節(jié)點(diǎn)就不需要再考慮了。這個(gè)時(shí)候整個(gè)需要考慮的樹減少了一層。以此類推直到根節(jié)點(diǎn)即為最終答案。 代碼實(shí)現(xiàn)