动态规划小结（1）最大子段和

print? 1.对于一维问题，求解一个序列中的连续子段的最大和。 
状态：一维数组dp[i]：以i结尾的最大子段和，并非前i项的最大子段和，二者有区别。 
转移：if dp[i]>0  
        dp[i+1]=dp[i]+a[i] 
      else 
        dp[i+1]=dp[i] 
       ans=max(dp[k];k=1,2,....n), 
空间上可以用滚动数组的原理优化，空间复杂度O(1)。 
      if ans>0 dp+=a[i] 
      else dp=a[i] 
      ans=max(dp) 
<A href="http://acm.hit.edu.cn/hoj/problem/view?id=1760" target=_blank>hoj 1760 The jackpot</A> 
 
2.二维。 
预处理出每行（列）的和，sum[i][j]表示第i行第1->j列的和。 
用O(n^3)的复杂度枚举所有的矩形，枚举一个行，两个列。 
对于一个矩形，行都缩为一个点，对列转化成为一维问题处理。 
hoj 2558 maxsum 
 
 
3.三维 
和二维转化成一维的情况完全类似。 
先预处理出底面（或其他面）的二维矩阵和。 
Sum[i][j][k]:第i层，对角端点为(1,1)和(j,k)的矩阵的元素和。 
然后用O(n^5)的复杂度枚举所有的立方体，将底面缩为一个点，对剩下一维作为一维处理。 
hoj 2555 

 1.对于一维问题，求解一个序列中的连续子段的最大和。
状态：一维数组dp[i]：以i结尾的最大子段和，并非前i项的最大子段和，二者有区别。
转移：if dp[i]>0
        dp[i+1]=dp[i]+a[i]
      else
        dp[i+1]=dp[i]
       ans=max(dp[k];k=1,2,....n),
空间上可以用滚动数组的原理优化，空间复杂度O(1)。
      if ans>0 dp+=a[i]
      else dp=a[i]
      ans=max(dp)
hoj 1760 The jackpot

2.二维。
预处理出每行（列）的和，sum[i][j]表示第i行第1->j列的和。
用O(n^3)的复杂度枚举所有的矩形，枚举一个行，两个列。
对于一个矩形，行都缩为一个点，对列转化成为一维问题处理。
hoj 2558 maxsum

3.三维
和二维转化成一维的情况完全类似。
先预处理出底面（或其他面）的二维矩阵和。
Sum[i][j][k]:第i层，对角端点为(1,1)和(j,k)的矩阵的元素和。
然后用O(n^5)的复杂度枚举所有的立方体，将底面缩为一个点，对剩下一维作为一维处理。
hoj 2555

补充：软件开发 , C++ ,

上一个：hoj 2555 三维最大子段和
下一个：hoj 1760 The jackpot一维