一、1050 To the Max：

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

//一維數組求最大字段

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記錄的是子段和的最大值

二維的情況：

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

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

二、1579 Function Run Fun

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

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)

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

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

三、1080 Humman Gene Function

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

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

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

       很早以前就看過這題，求最大遞增序列，那時剛剛曉得什么叫“動態規劃”，是《算法設計與分析》（王曉東）上的一道習題，開始不會做。后來想了一種很笨的辦法，用了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，是有很多路由器搭線，要求求出互不相交的搭配的最大個數。細細分析一下題目，只要被匹配的路由器序號是一個遞增的序列，則他們的連線就不會相交，就把這題轉化為求最大遞增序列的問題。但需要注意的是這題的問題規模n達到了40000，Time Limit :1000MS，所以在這里要選用剛才提到的O(nlogn)的算法，才不會導致TLE。

五、1014 Dividing

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

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

       六、2192 Zipper

       又是一道字符串的動態規劃題目，簡述一下：給出三個字符串，s1,s2,s3，s3的長度為s1與s2長度之和，判斷s1，s2是否為s3的不重合的公共子序列。其實就是判別公共之序列的升級版，把原來的一對一，改成了一對二。我用一個二維數組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)的時間，遞推能產生mark[c1][c2]的值，值為true輸出即能夠全部匹配。

       七、2576 Tug of War

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

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

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

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

       八、2441 Arrange the Bulls

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

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

       九、2738 Two Ends

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

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

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

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

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

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

那么第二個人的狀態轉移就相對比較好確定了：

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]的值，選其中最大的出來就行了^_^