清华大学出版社 动态规划算法 记b=m1≤j≤n,则所求的最大子段和为 mx∑q=mxmx∑]=mxb 当b1>0时b=b-1+a,否则b=a。由此可得计算b的 动态规划递归式 b]=maxb-1+a],a},1≤j≤n public static int maxSumO int n=a length-1 int sum=0 b=0 for(int i=1; i<=n; i++) if (>0)+=a] else b=a0 if (b>sum)sum=b return sum|算法显然需要O()计算时间和o()空间
6 动态规划算法 记 ，1 j n，则所求的最大子段和为 当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。由此可得计算b[j]的 动态规划递归式 [ ] max{ [ ]} 1 = = j k i i j b j a k max [ ] max max [ ] max [ ] 1 1 1 1 a k a k b j j n j k i j n i j j k i i j n = = = = b[j]=max{b[j-1]+a[j]，a[j]}， 1 j n 算法显然需要O(n)计算时间和O(n)空间。 public static int maxSum() { int n=a.length-1; int sum=0, b=0; for (int i=1;i<=n;i++) { if (b>0) b+=a[i]; else b=a[i]; if (b>sum)sum=b; } return sum; }
半大学出版社 最大子矩阵和问题 给定一个m行n列的整数矩阵a,试求矩阵a的一个子矩阵,使其 各元素之和为最大 记s(12,八,12)=∑∑ i=il j=jl 最大子矩阵和问题的最优值为Xmn2,八2) 由于mXm812,几1,12)=mXn{X2(,2,八,12)=mm2) 其中,12)=mB(121,12)=m∑∑ 设小4,则似2)=m 由于解最大子段和问题的动态规划算法需要时间o(n),故算 法的双重for循环需要计算时间O(m2n)
7 最大子矩阵和问题 记 最大子矩阵和问题的最优值为 由于 其中， 设 ，则 给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其 各元素之和为最大。 = = = 2 1 2 1 ( 1, 2, 1, 2) [ ][ ] i i i j j j s i i j j a i j max ( 1, 2, 1, 2) 1 1 2 1 1 2 s i i j j j j n i i m max ( 1, 2, 1, 2) max { max ( 1, 2, 1, 2)} max ( 1, 2) 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 s i i j j s i i j j t i i i i m j j n i i m j j n i i m = = = = = = 2 1 2 1 1 1 2 1 1 2 ( 1, 2) max ( 1, 2, 1, 2) max [ ][ ] j j j i i i j j n j j n t i i s i i j j a i j = = 2 1 [ ] [ ][ ] i i i b j a i j = = 2 1 1 1 2 ( 1, 2) max [ ] j j j j j n t i i b j 由于解最大子段和问题的动态规划算法需要时间O(n)，故算 法的双重for循环需要计算时间O(m2n)
清华大学出版社 最大m子段和问题 给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,以及 个正整数m,要求确定序列的m个不相交子段,使这m个子段的总 和达到最大。 设b(i,j表示数组a的前项中个子段和的最大值,且第个子段 含a](1≤i≤m,j≤n)。则所求的最优值显然为mwxb(m 与最大子段和问题类似地,计算b(,〕的递归式为 b(2j)=max{b(i,-1)+a[门,maxb(i-1,t)+a门}(l≤i≤m,i≤j≤n) i-1≤<j 初始时,b(0,j)=0,(1≤j≤n;b(,0)=0,(1≤i≤m)。 优化:注意到在上述算法中,计算b[时只用到数组b的第i-1 行和第行的值。因而算法中只要存储数组b的当前行,不必存 储整个数组。另一方面,b(i-1,t)的值可以在计算第i1行时预 先计算并保存起来。计算第行的值时不必重新计算,节省了计 算时间和空间
8 最大m子段和问题 给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,以及一 个正整数m，要求确定序列的m个不相交子段，使这m个子段的总 和达到最大。 设b(i，j)表示数组a的前j项中i个子段和的最大值，且第i个子段 含a[j](1 i m，i j n)。则所求的最优值显然为 与最大子段和问题类似地，计算b(i，j)的递归式为 初始时，b(0，j)=0，(1 j n);b(i，0)=0，(1 i m)。 max b(m, j) m jn ( , ) max{ ( , 1) [ ], max ( 1, ) [ ]} (1 , ) 1 b i j b i j a j b i t a j i m i j n i t j = − + − + − 优化：注意到在上述算法中，计算b[i][j]时只用到数组b的第i-1 行和第i行的值。因而算法中只要存储数组b的当前行，不必存 储整个数组。另一方面，b(i-1，t)的值可以在计算第i-1行时预 先计算并保存起来。计算第i行的值时不必重新计算，节省了计 算时间和空间
清华大学出版社 TSINGHUA UNIVERSITY PRESS 动态规划加速原理 四边形不等式
9 动态规划加速原理 四边形不等式
清华大学出版社 货物储运问题 PRESS 在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运 公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的 2堆集装箱合并成新的一堆,所需的运输费用与新的一堆中集 装箱数成正比。给定各堆的集装箱数,试制定一个运输方案, 使总运输费用最少。 设合并a,1≤jn,所需的最少费用为m[j,则原问题的最 优值为m[1,n]。由最优子结构性质可知, m小=1mnmk-1+m八+叫}1< t=l 根据递归式,按通常方法可设计计算m(i〕)的O(η3)动态规划算法
10 货物储运问题 在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运 公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的 2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集 装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案， 使总运输费用最少。 设合并a[i:j]，1≤i≤j≤n，所需的最少费用为m[i,j]，则原问题的最 优值为m[1，n]。由最优子结构性质可知， i j i j m i k m k j a t m i j j t i i k j = − + + = = min { [ , 1] [ , ] [ ]} 0 [ , ] 根据递归式，按通常方法可设计计算m(i,j)的O(n3 )动态规划算法