MyException - 我的异常网
当前位置:我的异常网» 编程 » 动态规划总结(1)最大子段和

动态规划总结(1)最大子段和

www.myexceptions.net  网友分享于:2013-04-10  浏览:8次
动态规划小结(1)最大子段和

 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


文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有