一、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]的值，选其中最大的出来就行了^_^