2、[i,j]的值，取出最小值即時(shí)m[i,j】的最優(yōu)化方案。遞推公式如下：可以根據(jù)上式得到一個(gè)遞歸算法。本題即是求m[l,n]的值。用二維數(shù)組m存儲(chǔ)的值，用二維數(shù)組s來儲(chǔ)存應(yīng)當(dāng)分割的位置。以本題中第一個(gè)矩陣a)<3,5,2,1,10>為例，可以得出如下矩陣：通過m數(shù)組可以得出最少的乘法次數(shù)，通過s數(shù)組可以輸出最優(yōu)方案。遇到的問題：在輸出S數(shù)組的結(jié)果的吋候仍然需要遞歸調(diào)用，需要合適的控制遞歸的條件?？偨Y(jié)：在矩陣鏈乘問題中可以看岀，動(dòng)態(tài)規(guī)劃結(jié)合遞歸的思想可以快捷的解決很多問題。木題屮，重點(diǎn)是歸納出m[ij]的遞推
3、公式。問題:LongestCommonSubsequence分析：本題即是最長(zhǎng)公共子序列問題。假設(shè)冇序列A[m]和序列B[n]，顯然，對(duì)于每一個(gè)都對(duì)應(yīng)著一個(gè)公共子序列的長(zhǎng)度。假設(shè)K度為c,就可以得到一個(gè)二維數(shù)組c[m,n】。對(duì)于c[i,j]，當(dāng)Ai=Bj的吋候，問題就轉(zhuǎn)變力求A[l..i-1]和B[l..j-1]的公共子序列長(zhǎng)度的問題，所以c[i，j]的長(zhǎng)度就是c[i-l，j-1]+1;同理，當(dāng)Ai!=Bj的時(shí)候，c[i,j]應(yīng)該在c[i-l,j]與c[i,j-l]中取最大值。另外，當(dāng)i或者j等于0的時(shí)候
4、，顯然c的值為0。由上面所述，可以得到遞推公式如下：為了解決這個(gè)問題，還如要定義另一個(gè)數(shù)組用于存放c數(shù)組中每一個(gè)元素的來源。這個(gè)來源其實(shí)就反映了公共子申。可以通過箭頭表示來源，相連的箭頭序列中指句左上方的箭頭最多的一率對(duì)應(yīng)的就是最K公共子序列。比如對(duì)于題□屮給出的第一個(gè)例子X:xzyzzyxY:zxyyzxz可以用一個(gè)矩陣表示計(jì)算的過程：遇到的問題：在算法中，‘=’是屬于‘<’還是‘>’會(huì)給結(jié)果帶來不同。在輸出子序列的吋候，最松公共子序列可能不止一個(gè)，似是最終未能解決還是只能輸出—個(gè)。總結(jié)：最K公共子序列
5、問題可以利用動(dòng)態(tài)規(guī)劃很好的解決。動(dòng)態(tài)規(guī)劃的思想就是根據(jù)規(guī)律獲得推導(dǎo)公式，然后解決問題。問題：LongestCommonSubstring分析：最長(zhǎng)公共子序列問題就是和最長(zhǎng)公共子申問題差不多，就是當(dāng)當(dāng)Ai!=Bj的時(shí)候，對(duì)應(yīng)的c[i，j]置為0。推導(dǎo)公式如下：最終c數(shù)組的最大值max對(duì)應(yīng)的就是最長(zhǎng)公共子審，只需耍將從本位置向前述max-1個(gè)的子串即是所求子串?？偨Y(jié)：本題就是第二題的一種特殊的情況，即C數(shù)組中的值不能從左和上兩個(gè)方向獲取，其他基本相同。在代碼上，只需耍修改小部分代碼就可以實(shí)現(xiàn)該問題。四、問題:
6、MaxSum分析：求和最大的子串。這個(gè)M題和第三題很像，不過這次不用二維數(shù)組而是使用兩個(gè)標(biāo)記來標(biāo)志所求子申的起始位置（maxb）結(jié)束位置（maxe）。思路是，對(duì)于第i個(gè)元素，如果當(dāng)前元素與目前選中的序列的sum小于0,那么這么序列不會(huì)被選擇，更新sumb與sume的值；如果sum仍然大于0，則sum可以選屮。比較sum與max的值，如果sum>max,則更新maxb與maxe的值。遞推公式如卜、遇到的問題：在全是負(fù)數(shù)吋出現(xiàn)問題，后來講max的初始值設(shè)置為第一個(gè)元素的值后就能正常了?？偨Y(jié)：動(dòng)態(tài)規(guī)劃能解決很多
7、問題，找到遞推公式非常重要。問題：Shortestpathinmultistagegraphs.Findtheshortestpathfrom0to15forthefollowinggraph.分析：觀察本題閣的特點(diǎn)，發(fā)現(xiàn)可以將閣分解為7個(gè)部分，以此可以計(jì)算到每一個(gè)節(jié)點(diǎn)的最短的路徑。即可求出最終的最短路徑?？偨Y(jié)：結(jié)合木題中的特殊情況，可以采用適當(dāng)?shù)姆椒▉硖幚怼５谌螌?shí)驗(yàn)問題：KnapsackProblem.Thereare5itemsthathaveavalueandweightlistbelow,the
8、knapsackcancontainatmost100Lbs.Solvetheproblembothasfractionalknapsackand0/1knapsack.value(SUS)2030654060weight(Lbs)1020304050value/weight21.52.111.2分析：本題是背包w題的兩個(gè)解法。對(duì)于部分背包來說比較簡(jiǎn)單，就是將單位價(jià)值大的物品優(yōu)先放置到背包中，這樣就能在背包中獲取最大的價(jià)值。但
