一、1050 To the Max：

       這是我的第一個(gè)DP，題目的意思很簡(jiǎn)單，在一個(gè)矩陣?yán)锩嬲宜淖泳仃嚕沟米泳仃嚁?shù)值之和到達(dá)最大。其實(shí)就是最大子段和問(wèn)題在二維空間上的推廣。先說(shuō)一下一維的情況吧。設(shè)有數(shù)組a0,a1…an,找除其中連續(xù)的子段，使它們的和達(dá)到最大。最開始的想法，是枚舉矩陣的長(zhǎng)度，計(jì)算每個(gè)子矩陣的和，然后比較得出最大值，這樣要消耗的時(shí)間為O(n)。讓我們?cè)傧胂耄绻@個(gè)序列的每一個(gè)數(shù)都是整數(shù)，那么它們的最大子段和就是把所有的數(shù)相加。所以我們想要盡可能多地找到正數(shù)相加。在序列中有負(fù)數(shù)的情況下，從頭開始掃描數(shù)組，把正數(shù)都相加，這其中可能會(huì)有負(fù)數(shù)，一種情況是：負(fù)數(shù)和減小子段和，但這時(shí)子段和仍然為正，用sum記錄下連續(xù)子段和的最大值，繼續(xù)想后掃描，因?yàn)楹竺嬗锌赡艹霈F(xiàn)更大的正數(shù)的情況，會(huì)使和比原來(lái)沒(méi)加負(fù)數(shù)之前更大；第二種情況是：加入一個(gè)負(fù)數(shù)后，是這個(gè)連續(xù)的子段和的值變成了負(fù)數(shù)，這時(shí)就要拋棄該負(fù)數(shù)以及該負(fù)數(shù)之前的所有序列，因?yàn)榍懊嫒粲凶佣闻c后面構(gòu)成了連續(xù)的子段，則這個(gè)子段一定會(huì)包括這個(gè)負(fù)數(shù)，而在這個(gè)負(fù)數(shù)之前的序列的和是個(gè)負(fù)數(shù)，那么這個(gè)子段的和一定不是最大的子段和。拋棄這個(gè)負(fù)數(shù)之前的序列后，子段和從這個(gè)負(fù)數(shù)后面的第一個(gè)數(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就是記錄當(dāng)前掃描過(guò)的子段和的，而sum記錄的是子段和的最大值

二維的情況：

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

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

二、1579 Function Run Fun

這肯定是一個(gè)處心積慮的函數(shù)，沒(méi)看出它有什么實(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)

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

總結(jié)：這道題是很地道的DP，因?yàn)樗淖訂?wèn)題實(shí)在是太多了，但還是屬于簡(jiǎn)單題目的范疇，就像把fabonacci函數(shù)增加到三維，限制條件多點(diǎn)而已，而實(shí)際上的做法都一樣。

三、1080 Humman Gene Function

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

感覺這題有點(diǎn)像求最長(zhǎng)公共子序列。只不過(guò)把求最大長(zhǎng)度改成了求最大的匹配值。用二維數(shù)組m[i][j]記錄字符串a中的第i個(gè)字符與字符串b中的第j個(gè)字符匹配所產(chǎn)生的最大值。若字符串a的長(zhǎng)度為la，字符串b的長(zhǎng)度為lb，初始時(shí)m[la][k](0<=k<=lb-1),這里即為字符串a的末尾與b中的字符匹配，因?yàn)槌^(guò)了字符串a的長(zhǎng)度，所以匹配的時(shí)候只能時(shí)以空格’-’匹配。同理可產(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

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

五、1014 Dividing

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

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

       六、2192 Zipper

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

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

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

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

       七、2576 Tug of War

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

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

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

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

       八、2441 Arrange the Bulls

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

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

       九、2738 Two Ends

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

       很容易想到DP，第二個(gè)人的取數(shù)規(guī)則是一定的，只有第一個(gè)個(gè)人可以選擇，那么在第一個(gè)人取數(shù)的時(shí)候就有狀態(tài)轉(zhuǎn)移方程，dp[i][j]表示前面是第i個(gè)數(shù)后面是第j個(gè)數(shù)的時(shí)候第一個(gè)人所能得到數(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ù)

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

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