noi竞赛算法学习动态规划

1、动态动态算法总体思想动态算法与分治法类似，其基本思想也是将待求解分解成若干个子。但是经分解得到的子往往不是互相的。不同子的数目常常只有多项式量级。在用分治法求解时，有些子被重复计算了许多次。如果能够保存已解决的子的，而在需要找出已求得的，就可以避免大量重复计算，从而得到多项式时间算法。动态基本步骤:(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3) 以自底向上的方式计算出最优值。(4) 根据计算最优值时得到的信息，构造最优解。实例一、完全加括号的矩阵连乘积可递归定义：（1） 单个矩阵是完全加括号的；（2） 矩阵连乘积 A 是完全加括号的 ，则 A 可表示为 2 个完全加括

2、号的矩阵连乘积 B 和 C的乘积并加括号，即 A = （BC）。设有四个矩阵 A,B,C,D 它们的维数分别是: A = 50*10 , B = 10*40 , C = 40*30 , D = 30*5总共有五中完全加括号的方式：例如：(A(BC)D): 10 * 40 * 30 + 10 * 30 * 50 + 50 * 30 * 5 = 34500给定矩阵A1, A2, A3,., An，其中 Ai 与A(i+1)是可乘的。i = 1,2,3, ., n - 1。这 n 个矩阵的连乘积 A1*A2*A3.An.由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序

3、可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用 2 个矩阵相乘的标准算法计算出矩阵连乘积。矩阵连乘给定矩阵A1, A2, A3,., An，其中 Ai 与A(i+1)是可乘的。i = 1,2,3, ., n - 1。这 n 个矩阵的连乘积 A1*A2*A3.An. 如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少.穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于 n 个矩阵的连乘积，设其不同的计算次序为 P(n)由

4、于每种加括号方式都可以分解为两个子矩阵的加括号(A1.Ak)(A(k+1)An)可以得到关于 P(n)的递推式如下：动态：将矩阵连乘积 A(i)A(i+1)A(j)简记为 Ai:j，这里 i <= j。计算 Ai:j的最优计算次序。设这个计算次序在矩阵 A(k)和A(k+1)之间将矩阵链断开，i <= k < j, 则其相应完全加括号(A(k+1)A(k+2).A(j)。(A(i)A(i+1).A(k) *计算量：Ai:k的计算量加上 Ak+1,j，再加上 Ai:k * Ak+1j的计算量。分析最优解的结构特征：计算 Ai:j的最优次序所包含的计算矩阵子链 Ai:k和 Ak+

5、1:j的次序也是最优的。矩阵连乘计算次序的最优解包含着其子的最优解。这种性质称为最优子结构性质。的最优子结构性质是该可用动态算法求解的显著特征。建立递归设计算 Ai:j，1 <= i <= j <= n，所需要的最少数乘次数 mi,j，则原m1,n当 i = j 时，Ai:j=Ai，因此，mi,i = 0，i = 1,2,n当 i < j 时，mi,j = mi,k + mk+1,j + p(i-1)p(k)p(j)这里 A(i)的维数为 p(i-1)*(i)(注：p(i-1)为矩阵 A(i)的行数，p(i)为矩阵 Ai的列数)的最优值为可以递归地定义 mi,j为：k

6、的位置只有 j - i 种。计算最优值对于 1 <= i <= j <= n 不同的有序对(i,j)对应于不同的子数最多只有：。因此，不同子的个（大括号表示 C(n,2)，组合的意思。后面的符号表示 “紧渐近界记号”）但是，在递归计算时，许多子又一显著特征。被重复计算多次。这也是该可用动态算法求解的用动态算法解此，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子。每个子只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。用动态法求最优解连乘矩阵假如为：计算过程为：从 m 可知最小连乘次数为 m16 = 15125从

7、s 可知计算顺序为(A1(A2A3)(A4A5)A6)实现：代码#include <iostream> #include <vector> using namespace std ;class matrix_chainpublic:matrix_chain(const vector<int> & c) cols = c ;count = cols.size () ; mc.resize (count) ; s.resize (count) ;for (int i = 0; i < count; + i) mci.resize (count) ;

8、 si.resize (count) ;for (int i = 0; i < count; + i) for (int j = 0; j < count; + j) mcij = 0 ;sij = 0 ;/ 使用备忘录计算void lookup_chain () lookup_chain (1, count - 1) ; min_count = mc1count - 1 ;cout << "min_multi_count = "<< min_count << endl ;/ 输出最优计算次序 trackback (1, co

9、unt - 1) ;/ 使用普通进行计算void calculate () int n = count - 1; / 矩阵的个数/r 表示每次宽度i,j 表示从从矩阵 i 到矩阵 j k 表示切割位置for (int r = 2; r <= n; + r) for(int i = 1; i <= n - r + 1; + i) int j = i + r - 1 ;/ 从矩阵 i 到矩阵 j 连乘，从 i 的位置切割，前半部分为 0 mcij = mci+1j + colsi-1 * colsi * colsj ; sij = i ;for (int k = i + 1; k &l

10、t; j; + k) int temp = mcik + mck + 1j + colsi-1 * colsk * colsj ;if (temp < mcij) mcij = temp ;sij = k ; / for k / for i / for rmin_count = mc1n ;cout << "min_multi_count = "<< min_count << endl ;/ 输出最优计算次序 trackback (1, n) ;private:int lookup_chain (int i, int j) / if

11、该最优解已求出，直接返回(mcij > 0) return mcij ;if(i = j) return 0 ;/ 不需要计算，直接返回/下面两行计算从 i 到 j 按照顺序计算的情况int u = lookup_chain (i, i) + lookup_chain (i + 1, j)+ colsi-1 * colsi * colsj ; sij = i ;for (int k = i + 1; k < j; + k) int temp = lookup_chain(i, k) + lookup_chain(k+ colsi - 1 * colsk * colsj ; if (

12、temp < u) u = temp ; sij = k ;+ 1,j)mcij = u ; return u ;void trackback (int i, int j) if (i = j) return ; trackback (i, sij) ; trackback (sij + 1, j) ;cout <<i<< "," << sij << " " << sij+ 1 << ","<< j<<endl;private:vec

13、tor<int> intcols ;/ 列数count;/ mc;矩阵个数+ 1/ 从第i 个矩阵乘到第j 个矩阵最小数vector<vector<int> >乘次数vector<vector<int> >s;/ 最小数乘的切分位置/ 最小数乘次数intmin_count ; ;算法复杂度分析：算法 matrixChain 的主要计算量取决于算法中对 r，i 和 k 的 3 重循环。循环体内的计算量为 O(1)，而 3 重循环的总次数为 O(n3)。因此算法的计算时间上界为 O(n3)。算法所占用的空间显然为 O(n2)。动态算法的基

14、本要素一、最优子结构矩阵连乘计算次序的最优解包含着其子的最优解。这种性质称为最优子结构性质。在分析的最优子结构性质时，所用的具有普遍性：首先假设由的最优解导出的最优解更好的解，子的解不是最优的，然后再设法说明在这个假设下可构造出比原从而导致。利用的最优子结构性质，以自底向上的方式递归地从子的最优解逐步构造出整个问题的最优解。最优子结构是能用动态算法求解的前提。同一个可以有多种方式刻划它的最优子结构，有些表示的求解速度更快（空间占用小，的维度低）二、重叠子int main()/ 初始化const int MATRIX_COUNT = 6 ; vector<int>c(MATRIX_C

15、OUNT + 1) ; c0 = 30 ;c1 = 35 ;c2 = 15 ;c3 = 5 ;c4 = 10 ;c5 = 20 ;c6 = 25 ;matrix_chain mc (c) ;/ mc.calculate () ; mc.lookup_chain () ; return 0 ;递归算法求解性质称为子时，每次产生的子并不总是新，有些子被反复计算多次。这种的重叠性质。动态算法，对每一个子只，而后将其解保一个表格中，当再次需要解此子时，只是简单地用常数时间查看一下结果。通常不同的子个数随的大小呈多项式增长。因此用动态算法只需要多项式时间，从而获得较高的解题效率。三、备忘录备忘录的结构与

16、直接递归的结构相同，区别在于备忘录为每个的子建立了备忘录以备需要时查看，避免了相同子的重复求解。实现（见矩阵连乘源码）实例二、最长公共子序列若给定的序列 X = x1,x2,xm,则另一序列 Z = z1,z2,zk，是 X 的子序列是指 一个严格下表序列i1,i2,ik使得对于所有的 j = 1,2,k 有 zj = xij。例如，序列 Z = B,C,D,B是序列 X = A,B,C,B,D,A,B的子序列，相应的递增下标序列为2,3,5,7。给定 2 个序列 X 和 Y，当另一序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X和 Y 的公共子序列。表述：给定 2 个序列

17、 X=x1,x2,xm和 Y = y1,y2,yn，找出 X 和 Y 的最长公共子序列。最长公共子序列的结构设序列 X = x1,x2,xm和 Y = y1,y2,yn的最长公共子序列为 Z =z1,z2,zk ，则(1)若xm = yn，则 zk = xm = yn，且 z(k-1)是 x(m-1)和 y(n-1)的最长公共子序列。(2)若xm != yn 且 zk != xm，则Z 是 x(m-1)和 Y 的最长公共子序列。(3)若xm != yn 且 zk != yn，则Z 是 X 和 y(n-1)的最长公共子序列。由此可见，2 个序列的最长公共子序列包含了这 2 个序列的前缀的最长公共

18、子序列。因此， 最长公共子序列具有最优子结构性质。子的递归结构最优值的递归。用 cij由最长公共子序列的最优子结构性质建立子序列 Xi 和 Yi 的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i = 0 或 j = 0 时，空序列是 Xi 和 Yj 的最长公共子序列。故此时 Cij = 0。其它情况下，由最优子结构性质可建立递归如下：由于在所考虑的子空间中，总共有 (mn)个不同的子底向上地计算最优值能提高算法的效率，因此，用动态算法自计算最优值和构造最长公共子序列（见源码）实现：代码#include <iostream> #include &l

19、t;vector> using namespace std ;/ longest common sequence class LonComSequencepublic:typedef vector<vector<int> >LCS_Type ; typedef vector<vector<int> >MarkType ;public:LonComSequence (const vector<char>& vSeq1,const vector<char>& vSeq2): mc_nEqual (1),

20、mc_nSq1move(2), mc_nSq2move(3)m_vSeq1 = vSeq1 ; m_vSeq2 = vSeq2 ; m_nLen1 = vSeq1.size() ; m_nLen2 = vSeq2.size() ;/ 初始化最长公共子序列的长度m_lcsLen.resize (m_nLen1 + 1) ; m_mtMark.resize (m_nLen1 + 1) ;for (int i = 0; i < m_nLen1 + 1; + i) m_lcsLeni.resize (m_nLen2 + 1) ; m_mtMarki.resize (m_nLen2 + 1) ;/

21、 计算最长公共子序列的长度int calLcsLength ()for (int i = 1; i <= m_nLen1; + i) m_lcsLeni0 = 0 ; / 序列二的长度为 0，公共子序列的长度为 0for (int i = 1; i <= m_nLen2; + i) m_lcsLen0i = 0 ; / 序列一的长度为 0，公共子序列的长度为 0for(int i = 0; i < m_nLen1; + i) for (int j = 0; j < m_nLen2; + j) if (m_vSeq1i = m_vSeq2j) m_lcsLeni+1j+1

22、 = m_lcsLenij + 1 ; m_mtMarki+1j+1 = mc_nEqual ;else if (m_lcsLenij+1 >= m_lcsLeni+1j)m_lcsLeni+1j+1 m_mtMarki+1j+1=m_lcsLenij+1 mc_nSq1move ;else m_lcsLeni+1j+1 m_mtMarki+1j+1=m_lcsLeni+1j;mc_nSq2move;return m_lcsLenm_nLen1m_nLen2;/ 构造最长公共子序列void LCS() cout << "LCS is : " ; LCS(m

23、_nLen1, m_nLen2); cout << endl ;private:void LCS (int i, intif (i = 0 | j = return ;j)0)if (m_mtMarkij=mc_nEqual) 1) ;- 1 << " " ; LCS (i - 1, j -cout << m_vSeq1ielse if (m_mtMarkij = mc_nSq1move) LCS (i - 1, j) ;else LCS (i, j - 1) ;private:vector<char> vector<c

24、har> intint LCS_Type MarkTypem_vSeq1 ; m_vSeq2 ;m_nLen1 m_nLen2/序列一序列二/ 序列一的长度/ 序列二的长度;m_lcsLen m_mtMark;/ 最长公共子序列的长度/m_lcsLenconst const constint int intmc_nEqual ; mc_nSq1move mc_nSq2move/ 相等的标志;/序列一左移的标志序列二左移的标志 ;intmain()vector<char> s1.push_back s1.push_back s1.push_back s1.push_back s

25、1.push_back s1.push_backs1 ; ('A')('B')('C')('D')('E')('F');vector<char> s2.push_back s2.push_back s2.push_back s2.push_back s2.push_backs2 ; ('B')('D')('F')('G')('H');LonComSequence lcs(s1, s2);cout <&l

26、t; lcs.calLcsLength () << endl ; lcs.LCS();return 0 ;算法的改进在算csLength 和 lcs 中，可数组 b 省去。事实上，数组元素 cij的值仅由 ci-1j-1，ci-1j和 cij-1这 3 个数组元素的值所确定。对于给定的数组元素 cij，可以不借助于数组 b 而仅借助于 c 本身在时间内确定 cij的值是由ci-1j-1，ci-1j和 cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组 c 的第 i 行和第 i-1 行。因此，用 2 行的数

27、组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至 O(min(m,n)。实例三、最大子表述n 个数(可能是负数）组成的序列 a1,a2,an.求该序列例如: 序列(-2,11,-4,13,-5,-2) ，最大子11 - 4 + 1320。（1） 穷举算法： O(n3), O(n2)（2） 分治法：将序列 a1:n从 n/2 处截成两段：a1:n/2, an/2+1:n：实例三、最大子表述n 个数(可能是负数）组成的序列 a1,a2,an.求该序列子序列的最大值。也就是例如: 序列(-2,11,-4,13,-5,-2) ，最大子11 - 4 + 1320。（1） 穷举算法：

28、 O(n3), O(n2)（2） 分治法：将序列 a1:n从 n/2 处截成两段：a1:n/2, an/2+1:n：一共三种情况：a.最大子b.最大子c.最大子出现在左边一段出现在右边一段中间的断点对于前两种情况，只需继续递归调用，而对于第三种情况：那么 S1+S2 是第三种情况的最优值。（3）动态定义 bj：法：含义：从元素 i 开始，到元素 j 为止的所有的元素最大的那个。的子段有多个，这些子段中的子那么：如果：bj-1 > 0, 那么 bj = bj-1 + aj如果：bj-1 <= 0,那么 bj = aj这样，显然，我们要求的最大子，是 bj数组中最大的那个元素。实现：代

29、码#include <iostream> #include <vector> using namespace std ;class MaxSubSumpublic:MaxSubSum (const vector<int>& intArr)m_vIntArr = intArr ;m_nLen = m_vIntArr.size () ;/ use divide and conquer int use_DAC ()m_nMssValue = use_DAC (0, m_nLen - 1) ;return m_nMssValue ;/ use dynamic

30、 programmingintuse_DP ()int intsum = 0 ; temp = 0;for(int i = if (temptempelse tempif (temp0; i < m_nLen; + i)> 0) += m_vIntArri ;= m_vIntArri ;> sum) sum = temp ;m_nMssValue = sum ; return sum ;private:int use_DAC (int left, int right)/ ifcout << left << "," <<

31、right (left = right) return (m_vIntArrleft > 0<< endl ;? m_vIntArrleft : 0) ;/左边区域的最大子int leftSum = use_DAC (left, (left + right) / 2) ;/ 右边区域的最大子int rightSum = use_DAC (left + right) / 2 + 1, right) ;/ 中间区域的最大子int int int int forsum1 max1 sum2 max2 (intsum1=i0000=;(left + right) / 2; i >

32、;= left; - i) += m_vIntArri ;if (sum1 > max1) 实例四、多边形是一个单人玩的，开始时有一个由 n 个顶点多边形的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符”+”或”*”。所有边依次用整数从 1 到 n 编号。第 1 步，将一条边删除。max1 = sum1 ;for (int i = (left + right) / 2 + 1; i <= right; + i) sum2 += m_vIntArri ;if (sum2 > max2) max2 = sum2 ;int max0 = max1 + max2 ;max0

33、 = (max0 > 0 ? max0 : 0) ;/ cout << max0 << ", " << leftSum << ", " << rightSum << endl ; return max (max0 , max (leftSum, rightSum) ;private:vector<int>m_vIntArr ;/ 整形序列intm_nLen ;/ 序列长度intm_nMssValue;/ 最大子 ;int main()vector<int>

34、; vArr ; vArr.push_back (-2) ;vArr.push_back (11) ;vArr.push_back (-4) ;vArr.push_back (13) ;vArr.push_back (-5) ;vArr.push_back (-2) ;MaxSubSum mss (vArr) ;cout << mss.use_DP () << endl ; return 0 ;随后 n-1 步按以下方式操作：(1) 选择一条边 E 以及由E 连接着的 2 个顶点 V1 和 V2；(2) 用一个新的顶点取代边 E 以及由E 连接着的 2 个顶点 V1 和

35、 V2。将由顶点 V1 和 V2 的整数值通过边 E 上的运算得到的结果赋予新顶点。最后，所有被删除，结束。的得分就是所剩顶点上的整数值。: 对于给定的多边形，计算最高得分。最优子结构性质按照顺时针顺序，多边形和顶点的顺序可以写成：op1, v1, op2, v2, , opn, vn在所给多边形中，从顶点 i(1 <= i <= n)开始，长度为 j(链中有 j 个顶点)的顺时针链 p(i， j) 可表示为vi, opi+1, vi+1, opi+j-1, vi+j-1如果这条链在 opi + s处进行最后一次合并运算(1 <= s <= j-1)，则可在 opi+s

36、处将链分割为 2 个子链：从 i 开始长度为 s 的链： p(i，s)从 i + s 开始，长度为 j - s 的链：p(i + s，j-s)。设:m1 是对子链 p(i，s)的任意一种合并方式得到的值，而 a 和 b 分别是在所有可能的合并中得到的最小值和最大值。m2 是 p(i+s，j-s)的任意一种合并方式得到的值，而 c 和 d 分别是在所有可能的合并中得到的最小值和最大值。依此定义有 a <= m1 <= b，c <= m2 <= d(1)当 opi+s = +时，显然有 a + c <= m <= b + d (2)当 opi+s = *时，有m

37、in ac，ad，bc，bd <= m <= max ac，ad，bc，bd换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。实现：代码#include <iostream> #include <vector>using namespace std ;struct SegInfopublic:SegInfo (): m_nMaxValue (0), m_nMinValue(0)SegInfo (int maxValue, int minValue): m_nMaxValue (maxValue), m_nMinValue (minValue)pub

38、lic:int m_nMaxValue ; int m_nMinValue ; ;class PolyGamepublic:PolyGame (const vector<char>& op, const vector<int>& vertex)m_vcOp = op ; m_vnVertex = vertex ;m_nCount = m_vcOp.size () ;m_vSeg.resize (m_nCount) ;for (int i = 0; i < m_nCount; + i) m_vSegi.resize (m_nCount) ;intbe

39、ginCalulate ()/ 初始边界for (int i = 1; i < m_nCount; + i) m_vSegi1.m_nMaxValue = m_vnVertexi ; m_vSegi1.m_nMinValue = m_vnVertexi ;/ i: 起点/ j: 长度/ s: 子切分位置for (int j = 2; j < m_nCount ; + j) for (int i = 1; i < m_nCount; + i) for (int s = 1; s < j; + s) SegInfo si = calMinAndMax(i, s, j) ;i

40、f (m_vSegij.m_nMinValue > si.m_nMinValue) m_vSegij.m_nMinValue = si.m_nMinValue ;if (m_vSegij.m_nMaxValue < si.m_nMaxValue) m_vSegij.m_nMaxValue = si.m_nMaxValue ;/ 找到最大值int temp = m_vSeg1m_nCount - 1.m_nMaxValue ; for (int i = 2; i < m_nCount; + i) if (temp < m_vSegim_nCount - 1.m_nMaxValue) temp = m_vSegim_nCount - 1.m_nMaxValue