一、1050 To the Max：

       這是我的第一個DP，題目的意思很簡單，在一個矩陣里面找它的子矩陣，使得子矩陣數(shù)值之和到達最大。其實就是最大子段和問題在二維空間上的推廣。先說一下一維的情況吧。設有數(shù)組a0,a1…an,找除其中連續(xù)的子段，使它們的和達到最大。最開始的想法，是枚舉矩陣的長度，計算每個子矩陣的和，然后比較得出最大值，這樣要消耗的時間為O(n)。讓我們再想想，如果這個序列的每一個數(shù)都是整數(shù)，那么它們的最大子段和就是把所有的數(shù)相加。所以我們想要盡可能多地找到正數(shù)相加。在序列中有負數(shù)的情況下，從頭開始掃描數(shù)組，把正數(shù)都相加，這其中可能會有負數(shù)，一種情況是：負數(shù)和減小子段和，但這時子段和仍然為正，用sum記錄下連續(xù)子段和的最大值，繼續(xù)想后掃描，因為后面有可能出現(xiàn)更大的正數(shù)的情況，會使和比原來沒加負數(shù)之前更大；第二種情況是：加入一個負數(shù)后，是這個連續(xù)的子段和的值變成了負數(shù)，這時就要拋棄該負數(shù)以及該負數(shù)之前的所有序列，因為前面若有子段與后面構(gòu)成了連續(xù)的子段，則這個子段一定會包括這個負數(shù)，而在這個負數(shù)之前的序列的和是個負數(shù)，那么這個子段的和一定不是最大的子段和。拋棄這個負數(shù)之前的序列后，子段和從這個負數(shù)后面的第一個數(shù)算起，繼續(xù)掃描。

//一維數(shù)組求最大字段

int submax1(int a[], int n)

{

       int b=0;

       int bn=-32767;

       int i;

       int sum=0;

       for(i=0; i<n; i++)

       {

              if(b>0)

              {

                     b+=a[i];

              }

              else if(a[i]>bn && a[i]<0)

              {

                     bn=a[i];

                     b=a[i];

              }

              else

              {

                     b=a[i];

              }

              if(b>sum)

              {

                     sum=b;

              }

       }

       if(sum==0)

              return bn;

       else

              return sum;

}

其中變量b就是記錄當前掃描過的子段和的，而sum記錄的是子段和的最大值

二維的情況：

       這里我使用了一個很簡單的做法，在二維數(shù)組a[i][j]里面枚舉第一維的長度k，然后得到一個k*n的子矩陣，把這個子矩陣的每一列數(shù)值相加，就把這個二維數(shù)組轉(zhuǎn)化成了一維，再調(diào)用函數(shù)int submax1(int a[], int n)，就計算得出最大值。

總結(jié)：感覺我做這道題目還不是很像DP，只有在求一維情況下的sum記錄最大值，以及在掃描是計算的子段和b，代表了某數(shù)前面連續(xù)的最大子段和。

二、1579 Function Run Fun

這肯定是一個處心積慮的函數(shù)，沒看出它有什么實際的用處

Consider a three-parameter recursive function w(a, b, c):
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

這本身就是一個遞歸函數(shù)，要是按照函數(shù)本身寫遞歸式，結(jié)果肯定是TLE，這里我開了一個三維數(shù)組，從w(0,0,0)開始遞推，逐步產(chǎn)生到w(20,20,20)的值，復雜度O(n^3)

總結(jié)：這道題是很地道的DP，因為它的子問題實在是太多了，但還是屬于簡單題目的范疇，就像把fabonacci函數(shù)增加到三維，限制條件多點而已，而實際上的做法都一樣。

三、1080 Humman Gene Function

應該說這是一道比較經(jīng)典的DP，兩串基因序列包含A、C、G、T，每兩個字母間的匹配都會產(chǎn)生一個相似值，求基因序列（字符串）匹配的最大值。

感覺這題有點像求最長公共子序列。只不過把求最大長度改成了求最大的匹配值。用二維數(shù)組m[i][j]記錄字符串a中的第i個字符與字符串b中的第j個字符匹配所產(chǎn)生的最大值。若字符串a的長度為la，字符串b的長度為lb，初始時m[la][k](0<=k<=lb-1),這里即為字符串a的末尾與b中的字符匹配，因為超過了字符串a的長度，所以匹配的時候只能時以空格’-’匹配。同理可產(chǎn)生m[k][lb](0<=k<=la-1)，的所有值，再以此往前遞推，其狀態(tài)轉(zhuǎn)移方程為

m[i][j]=max{map[i][j]+m[i+1][j+1],m[‘-‘][j]+m[i][j+1],m[i][‘-’]+m[i+1][j]}

所以最后m[0][0]即為所求。

四、2533 Longest Ordered Subsequence

       很早以前就看過這題，求最大遞增序列，那時剛剛曉得什么叫“動態(tài)規(guī)劃”，是《算法設計與分析》（王曉東）上的一道習題，開始不會做。后來想了一種很笨的辦法，用了O(n^2)的時間，還附加了n^2的空間。看了世銘的兩種方法，一種是O(n^2),一種是O(nlogn)。兩種方法核心的方法都一樣，用一個n大小的一維空間(a[n])，a[i]表示子串長度為i時所有子串最大值中的最小值，因為要找一個i長度的子串，那么a[i]的值至少要比長度為i-1子串中的一個最末位的值要大。之所以會有兩種時間復雜度的差別，就是在查找i-1長度的末尾值中的最小值的時候，前者是線性的搜索，后者是用的二分搜索，提高了時間效率。另外說一下這題的變形吧，1631 Briging signals，是有很多路由器搭線，要求求出互不相交的搭配的最大個數(shù)。細細分析一下題目，只要被匹配的路由器序號是一個遞增的序列，則他們的連線就不會相交，就把這題轉(zhuǎn)化為求最大遞增序列的問題。但需要注意的是這題的問題規(guī)模n達到了40000，Time Limit :1000MS，所以在這里要選用剛才提到的O(nlogn)的算法，才不會導致TLE。

五、1014 Dividing

       實際上早就看到這題了，那時對ACM的認識還很幼稚，剛學完程序設計，學會怎么用遞歸，也不看題目的條件，反正就是六種marble，寫了個遞歸的程序，測試數(shù)據(jù)當然能通過，但其結(jié)果肯定是TLE了。又過了一段時間，有了點時間效率的觀念，寫了個枚舉法計算總和的1/2的可達性，不過還是有很多情況我都沒有考慮到，結(jié)果WA了。到現(xiàn)在學DP，再來看想想這題，其實還有更好的解法。也是計算總和的1/2(sum)的可達性，如果marble的總數(shù)是n，則DP算法的時間復雜度可以達到O(n*sum)。用一個一維數(shù)組標記從0－sum所有加和的可達性，對于一顆寶石的價值i，數(shù)組a[j]==true，表示和為j可達，那么可得出

a[i+j]=true,即i+j的值可達。循環(huán)以致于用完所有的寶石，觀察a[sum]的值，true即為這些寶石可分，反之不可分。

       六、2192 Zipper

       又是一道字符串的動態(tài)規(guī)劃題目，簡述一下：給出三個字符串，s1,s2,s3，s3的長度為s1與s2長度之和，判斷s1，s2是否為s3的不重合的公共子序列。其實就是判別公共之序列的升級版，把原來的一對一，改成了一對二。我用一個二維數(shù)組mark[i][j]記錄s1中的第i個字符以及s2中的第j個字符能否與s3[i+j]想匹配。

       If(s1[i]==s3[i+j]) mark[i+1][j]=true;//s1中的第i個字符匹配，則s1串向后移一個字符

       If(s2[j]==s3[i+j]) mark[i][j+1]=true;//s2中的第j個字符匹配，則s2串向后移一個字符

這樣用O(n^2)的時間，遞推能產(chǎn)生mark[c1][c2]的值，值為true輸出即能夠全部匹配。

       七、2576 Tug of War

       我覺得非常有必要做的一道題目。這道題目看似很簡單，實質(zhì)就是n個數(shù)，將其分成兩堆，兩堆數(shù)量的差距不超過1，并且使這兩堆數(shù)字之和最接近。是一道動態(tài)規(guī)劃題目，看起來簡單是因為受了1014題的影響，但這題兩堆的數(shù)目是確定的，一堆是n/2個，另一堆則是n-n/2個,而1014題是不受加和數(shù)目的影響的。這題也不同與多米勒骨牌那題，因為那題中各個數(shù)字之間是一一對應的。苦想了一天沒有結(jié)果，看來這題還要尋求其它的方法。這題不是我自己想除來的，看了alpc02的代碼，自己又照自己的理解重寫了一遍。

       記錄狀態(tài)是用一個二維數(shù)組，mark[i][j]表示i個數(shù)相加，其值能否達到j，如果能mark[i][j]的為true。對于一個輸入的數(shù)w，修改i個數(shù)的每一種狀態(tài)，其狀態(tài)轉(zhuǎn)移方程：

       If(m[i][j]) then m[i][j+w]=true;//j+w的值可由j的值加得

由后往前修改每一個i下的可達值。那么最后就只要再n/2行中找出m[n/2][j]的最大值（j<=total/2），這就是兩堆之和最接近的一組數(shù)值。

       八、2441 Arrange the Bulls

       這題里我看到了動態(tài)規(guī)劃的一種新的方法。每頭牛有自己喜歡的籃球場，我們的任務就是安排這些牛到它們喜歡的籃球場去，然后計算所有合理的解的數(shù)量（籃球場的數(shù)目最多20個）。顯然，要找到一個解，很容易就能搜出，但是要求所有解的數(shù)量，如果再用搜索的方法，在時間上是不堪忍受的。這里用了一種新的方法（對于我來說是一種新方法^_^）。用二進制數(shù)記錄當前籃球場使用的狀態(tài)，“1”表示未分配，“0”表示已分配，每個籃球場與每個數(shù)位相對應。所以20個籃球場就總共需要一個1<<20的數(shù)組來記錄所有生成的狀態(tài)。想到這里，我覺得這題基本上已經(jīng)解決一半了，剩下的就是如何進行狀態(tài)轉(zhuǎn)移，用的就是二進制運算。我覺得我在這個方面一點都不熟悉，不會寫，看了別人的代碼，然后自己仿寫了。

一種是用滾動數(shù)組，這種方法占用時間空間都較大，另一種是狀態(tài)壓縮的DP，方法比較巧妙。呵呵，要講得更深點，等我變成牛人在續(xù)吧……

       九、2738 Two Ends

       有點想博弈的題目，我事用dp來做的。有一組數(shù)，兩個人分別輪流從數(shù)組兩頭取數(shù)，第一個取數(shù)的人可以選用任意的策略，第二個人則要一直使用貪心策略。問最后第一個人所取得的數(shù)字之和比第二個人取得的數(shù)字之和最多多多少。

       很容易想到DP，第二個人的取數(shù)規(guī)則是一定的，只有第一個個人可以選擇，那么在第一個人取數(shù)的時候就有狀態(tài)轉(zhuǎn)移方程，dp[i][j]表示前面是第i個數(shù)后面是第j個數(shù)的時候第一個人所能得到數(shù)字和的最大值。

if(dp[i][j]+a[i]>dp[i+1][j])

                                   dp[i+1][j]=dp[i][j]+a[i];              //取前面的數(shù)

                            if(dp[i][j]+a[j]>dp[i][j-1])

                                   dp[i][j-1]=dp[i][j]+a[j];        //取后面的數(shù)

那么第二個人的狀態(tài)轉(zhuǎn)移就相對比較好確定了：

if(a[i]<a[j] && dp[i][j]!=-1 && dp[i][j]>dp[i][j-1])

                            dp[i][j-1]=dp[i][j];

                     if(a[i]>=a[j] && dp[i][j]!=-1 && dp[i][j]>dp[i+1][j])

                            dp[i+1][j]=dp[i][j];

最后一步只需比較dp[i][i]的值，選其中最大的出來就行了^_^