noip教程-动态规划的优化.ppt

《noip教程-动态规划的优化.ppt》由会员分享，可在线阅读，更多相关《noip教程-动态规划的优化.ppt（43页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、动态规划的优化方法动态规划的优化方法YALI 朱全民朱全民动态规划优化的内涵uu动态规划算法的时间复杂度=阶段数*每个阶段状态转移的状态数 *每次状态转移的时间 或者:状态总数*每次状态转移的时间uu重点:减少每个阶段的状态数，也就是减少了状态总数优化方法1：改进状态的表示uu例例1：理想收入：理想收入问题uu理想收入是指在股票交易中，以1元为本金可能获得的最高收入，并且在理想收入中允许有非整数股票买卖。uu已知股票在第i天每股价格是Vi元，1iM，求M天后的理想收入。方法一uu设Fi表示在第i天收盘时能达到的最高收入，则有Fi的递推关系式：公式含义：在第i天收盘时能达到的最高的收入，是将第j

2、天收盘后的收入，全部用于买入第k天的股票，再在第i天将所持的股票全部卖出所得的收入。时间复杂度是O(M3)。方法二uu设Pi表示前i天能获得的最多股票数，则可列出状态转移方程：uu设Qi表示前i天能达到的最大收入，则可列出状态转移方程：时间复杂度是O(M2)。方法三uu分析：上述公式的含义是当分析：上述公式的含义是当0=ji 0=ji 时时,求求Qi-1Qi-1和和Qj*vi/vjQj*vi/vj的最大值的最大值 uu对于对于0=ji0=ji，要求，要求Qi,Qi,实际上实际上Q1Qi-1Q1Qi-1都都已经求出，因此我们只要搞一个变量保存已经求出，因此我们只要搞一个变量保存Qj/Vj Qj/

3、Vj 的最大值即可，记为的最大值即可，记为MaxQ.MaxQ.uu这样，公式可以写成这样，公式可以写成uu对每次求出的对每次求出的Qi,Qi,都更新都更新MaxQ,MaxQ,显然时间复杂度显然时间复杂度为为O(M)O(M)问题描述现有n首由RaucousRockers演唱组录制的歌曲，计划从中选择一些歌曲来发行m张唱片，每张唱片至多包含t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择：(1)这组唱片中的歌曲必须按照它们创作的顺序排序；(2)包含歌曲的总数尽可能多。输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出

4、所能包含的最多的歌曲数目。例2RaucousRockers演唱组设n首歌曲按照创作顺序排序后的长度为long1.n，则动态规划的状态表示描述为：gi,j,k，(0in，0jm，0kt),表示前i首歌曲，用j张唱片另加k分钟来录制，最多可以录制的歌曲数目。状态转移方程为：当klongi，i1时：gi,j,k=maxgi-1,j,k-longi+1，gi-1,j,k当klongi，i1时：gi,j,k=maxgi-1,j-1,t-longi+1，gi-1,j,k规划的边界条件为：当0jm，0kt时：g0,j,k=0;问题的最优解为：gn,m,0。算法的时间复杂度为：O(n*m*t)。改进的状态表示

5、描述为：gi,j=(a,b)，0in，0ji，0am，0bt，表示在前i首歌曲中选取j首录制所需的最少唱片为：a张唱片另加b分钟。状态转移方程为：gi,j=mingi-1,j，gi-1,j-1+longi其中(a,b)+longi=(a,b)的计算方法为：当b+longit时：a=a;b=b+longi;当b+longit时：a=a+1;b=longi;规划的边界条件：当0in时，gi,0=(0,0)题目所求的最大值是：answer=maxk|gn,k(m-1,t)算法的时间复杂度为：O(n2)。优化方法优化方法2：利用决策的单调性利用决策的单调性uu例3：最长上升序列问题 f(i)=maxf

6、(j)+1 (1=ji f(i)=maxf(j)+1 (1=ji=n=n,bjbi),bjbi)uu上上式式含含义义为为：对对于于所所有有的的1=ji1=ji，bjbi,bjbi,必必须须找一个最大的找一个最大的f(j)f(j)uu反反过过来来说说，对对于于1=ji1=ji，必必须须找找到到一一个个最最大的大的f(j),f(j),满满足足bjbibjbi。分析uu对方程进行一下改进：对于对方程进行一下改进：对于对方程进行一下改进：对于对方程进行一下改进：对于 ji,ji,fi=maxf(j)+1,fi=maxf(j)+1,其中，其中，其中，其中，minj|r jaiminj|r jaiuurj

7、rjrjrj为为为为所有等于所有等于所有等于所有等于fjfjfjfj时时时时ajajajaj的最小的最小的最小的最小值值值值。uu因此，我因此，我因此，我因此，我们们们们可以搞一个可以搞一个可以搞一个可以搞一个队队队队列列列列维护维护维护维护f(j)f(j)f(j)f(j)的上升序列。的上升序列。的上升序列。的上升序列。uu对对对对于当前的于当前的于当前的于当前的i i i i，利用二分，利用二分，利用二分，利用二分查查查查找在找在找在找在队队队队列列列列查查查查找到找到找到找到满满满满足条足条足条足条件件件件bjbibjbibjbibjbi的的的的f(j)f(j)f(j)f(j)uu用用用用

8、bibibibi去替去替去替去替换换换换与与与与f(i)f(i)f(i)f(i)相等的相等的相等的相等的bjbjbjbj若若若若bj=bi,bj=bi,bj=bi,bjbibjbibjbibjbi，则则则则用用用用bibibibi替替替替换换换换bjbjbjbj若在若在若在若在对对对对尾，尾，尾，尾，则则则则直接插入直接插入直接插入直接插入uu显显显显然然然然该该该该算法的算法的算法的算法的时间时间时间时间复复复复杂杂杂杂度度度度为为为为O(n*log(n)O(n*log(n)O(n*log(n)O(n*log(n)例例4 4：最大子序和：最大子序和问题描述输入一个长度为的整数序列（A1,A2

9、,An），从中找出一段连续的长度不超过M的子序列，使得这个序列的和最大。最大子序和输入一个长度为的整数序列（输入一个长度为的整数序列（A1,A2,An），从中），从中找出一段长度不超过找出一段长度不超过m的连续的子序列，使得这个序列的和的连续的子序列，使得这个序列的和最大。最大。例如：序列例如：序列 1，-3，5，1，-2，3当当M=2或或3时时,S=5+1=6当M=4时,S=5+1-2+3=7数据范围:50%的数据N,M=1000100%的数据N,M=20000一个简化的问题序列的最大连续和输入一个长度为的整数序列（A1,A2,An），从中找出一段连续的子序列，使得这个序列的和最大。和原问题

10、相比没有M这个序列长度的限制！设F(i)表示以第i个数结尾的最大连续和以第i个数结尾的最大连续和序列，可能存在两种选择：情形一：只包含Ai情形二：包含Ai和以Ai-1结尾的最大连续和序列状态转移方程如下：F(i)=maxAi,F(i-1)+Ai边界：F(1)=A1，Ans=maxF(i)|1=i=n该算法的时间复杂度为O(n)分析算法一枚举设F(i)为以Ai结尾长度不超过M的最大子序和对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。该算法的时间复杂度为O(n2)简化方程用一个二叉堆来维护S(i-k)，每次求F(i)之前的操作如下：算法二堆求F(i-1)时，求minS(i-m-1

11、),S(i-2)求F(i)时，求minS(i-m),S(i-1)在堆中删除元素S(i-m-1)，插入元素S(i-1).复杂度O(2log2n)从堆中取出当前最小值.复杂度O(1)所以计算的总复杂度为O(nlog2n)队列优化在算法二中，考虑用队列来维护决策值S(i-k)。每次只需要在队首删掉S(i-m-1)，在队尾添加S(i-1)。但是取最小值操作还是需要O(n)时间复杂度的扫描。考察在添加S(i-1)的时候，设现在队尾的元素是S(k)，由于ki-1，所以S(k)必然比S(i-1)先出队。若此时S(i-1)=S(k)，则S(k)这个决策永远不会在以后用到，可以将S(k)从队尾删除掉（此时队列的

12、尾部形成了一个类似栈的结构）队列优化队列优化 同理，若队列中两个元素同理，若队列中两个元素S(i)和和S(j)，若若i=S(j)，则我们可以删掉，则我们可以删掉S(i)（因为（因为S(i)永远不会被用到）。此时的队永远不会被用到）。此时的队列中的元素构成了一个单调递增的序列，列中的元素构成了一个单调递增的序列，即：即：S1S2S3Sk算法三算法三 我们来整理在求我们来整理在求F(i)的时候，用队列的时候，用队列维护维护S(i-k)所需要的操作：所需要的操作：若当前队首元素若当前队首元素S(x)，有，有x=i-m为为止。止。若当前队尾元素若当前队尾元素S(k)=S(i-1)，则，则S(k)出队；

13、直到出队；直到S(k)S(i-1)为止。为止。在队尾插入在队尾插入S(i-1)取出队列中的最小值，即队首元素。取出队列中的最小值，即队首元素。算法三算法三 由于对于求每个由于对于求每个F(i)的时候，进队和的时候，进队和出队的元素不止一个。出队的元素不止一个。但是我们可以通过分摊分析得知，每但是我们可以通过分摊分析得知，每一个元素一个元素S(i)只进队一次、出队一次，所只进队一次、出队一次，所以队列维护的时间复杂度是以队列维护的时间复杂度是O(n)。而每次。而每次求求F(i)的时候取最小值操作的复杂度是的时候取最小值操作的复杂度是O(1)，所以这一步的总复杂度也是，所以这一步的总复杂度也是O(

14、n)。综上所述，该算法的总复杂度是综上所述，该算法的总复杂度是O(n)方法3：根据最优解的性质减少决策uu例例5 5：石子合并问题：石子合并问题规划的边界条件为：mi,i=0令si,j=k，表示合并的最优断开位置。算法的时间复杂度为O(n3)。猜想uu合并第i堆到第j堆石子的最优断开位置si,j要么等于i，要么等于j-1，也就是说最优合并方案只可能是：(i)(i+1 j)或 (i j-1)(j)证明：uu设合并第设合并第i i堆到第堆到第j j堆石子的最优断开位置堆石子的最优断开位置 si,j=p si,j=p，且，且ipj-1ipj-1。情况情况1 1：ti,ptp+1,j ti,ptp+1

15、,j uu 由于由于ipip，所以可以设，所以可以设q=si,pq=si,p。于是最优合并方案为：。于是最优合并方案为：(iq)(q+1.p)(p+1j)(iq)(q+1.p)(p+1j)，它的得分，它的得分，F1=mi,q+mq+1,p+mp+1,j+ti,j+F1=mi,q+mq+1,p+mp+1,j+ti,j+ti,pti,puu我们可以构造如下的合并方案：我们可以构造如下的合并方案：(iq)(q+1.p)(p+1j)(iq)(q+1.p)(p+1j)，它的得分，它的得分，F2=mi,q+mq+1,p+mp+1,j+ti,j+F2=mi,q+mq+1,p+mp+1,j+ti,j+tq+1

16、,jtq+1,juu由于由于qpqp，所以，所以ti,ptp+1,jtq+1,jti,ptp+1,jtq+1,j，所以，所以F1F2F1tp+1,j ti,ptp+1,j 与情况与情况1 1是对称的。是对称的。方法4:利用贪心思想减少状态总数uu例例例例6 6 6 6：快餐问题：快餐问题：快餐问题：快餐问题uuPeterPeter最近在最近在最近在最近在RR市开了一家快餐店，为了招揽顾客，该快餐店市开了一家快餐店，为了招揽顾客，该快餐店市开了一家快餐店，为了招揽顾客，该快餐店市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由准备推出一种套餐，该套餐由准备推出一种套餐，该套餐由准

17、备推出一种套餐，该套餐由AA个汉堡，个汉堡，个汉堡，个汉堡，BB个薯条和个薯条和个薯条和个薯条和C C个饮料个饮料个饮料个饮料组成。价格便宜。为了提高产量，组成。价格便宜。为了提高产量，组成。价格便宜。为了提高产量，组成。价格便宜。为了提高产量，PeterPeter从著名的麦当劳公司从著名的麦当劳公司从著名的麦当劳公司从著名的麦当劳公司引进了引进了引进了引进了NN条生产线。所有的生产线都可以生产汉堡，薯条和饮条生产线。所有的生产线都可以生产汉堡，薯条和饮条生产线。所有的生产线都可以生产汉堡，薯条和饮条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、

18、不同料，由于每条生产线每天所能提供的生产时间是有限的、不同料，由于每条生产线每天所能提供的生产时间是有限的、不同料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得的，而汉堡，薯条和饮料的单位生产时间又不同。这使得的，而汉堡，薯条和饮料的单位生产时间又不同。这使得的，而汉堡，薯条和饮料的单位生产时间又不同。这使得PeterPeter很为难，不知道如何安排生产才能使一天中生产的套餐很为难，不知道如何安排生产才能使一天中生产的套餐很为难，不知道如何安排生产才能使一天中生产的套餐很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序

19、，计算一天中套餐的最大生产量。为产量最大。请你编一程序，计算一天中套餐的最大生产量。为产量最大。请你编一程序，计算一天中套餐的最大生产量。为产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过简单起见，假设汉堡、薯条和饮料的日产量不超过简单起见，假设汉堡、薯条和饮料的日产量不超过简单起见，假设汉堡、薯条和饮料的日产量不超过100100个。个。个。个。uu输入输入输入输入:第一行为三个不超过第一行为三个不超过第一行为三个不超过第一行为三个不超过100100的正整数的正整数的正整数的正整数AA、BB、C C中间以一个中间以一个中间以一个中间以一个空格分

20、开。第二行为空格分开。第二行为空格分开。第二行为空格分开。第二行为3 3个不超过个不超过个不超过个不超过100100的正整数的正整数的正整数的正整数p1,p2,p3p1,p2,p3分别分别分别分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为第三行为第三行为第三行为N(0=0=10)N(0=0=10)，第四行为，第四行为，第四行为，第四行为NN个不超过个不超过个不超过个不超过1000010000的的的的正整数，分别为各

21、条生产流水线每天提供的生产时间，中间以正整数，分别为各条生产流水线每天提供的生产时间，中间以正整数，分别为各条生产流水线每天提供的生产时间，中间以正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。一个空格分开。一个空格分开。一个空格分开。uu输出输出输出输出:每天套餐的最大产量。每天套餐的最大产量。每天套餐的最大产量。每天套餐的最大产量。分析uu设设pi,j,kpi,j,k表表示示前前i i条条生生产产线线生生产产j j个个汉汉堡堡，k k个个薯薯条的情况下最多可生产饮料的个数。条的情况下最多可生产饮料的个数。uu用用ri,j,kri,j,k表表示示第第i i条条生生产产线线

22、生生产产j j个个汉汉堡堡，k k个个薯薯条的情况下最多可生产饮料的个数。条的情况下最多可生产饮料的个数。uu状态转移方程如下：状态转移方程如下：pi,j,k pi,j,k=Maxpi-1,j1,k1+ri,j-j1,k-Maxpi-1,j1,k1+ri,j-j1,k-k1k1uu约约束条件：束条件：(0=j1=j=100,0=k1=k=100,(0=j1=j=100,0=k1=k=100,&(&(j-j1)*p1+(k-k1)*p2=Ti)j-j1)*p1+(k-k1)*p2=Ti)ri,j-j1,k-k1=(Ti-(j-j1)*p1+(k-k1)*p2)ri,j-j1,k-k1=(Ti-(

23、j-j1)*p1+(k-k1)*p2)div p3;div p3;uu此算法的时间复杂度为此算法的时间复杂度为O(N*100O(N*1004 4),),优化uu在在本本题题中中，可可以以在在动动态态规规划划方方法法中中加加入入了了贪贪心心算算法法思思想想：即即首首先先计计算算出出每每天天生生产产套套数数的的上上限限值值（由由A,B,CA,B,C计计算算，即即minmin100 100 div div A A，100 100 div div B B，100 100 div div c c），接接着着，用用贪贪心心法法计计算算出出这这N N条条流流水水线线可可以以生生产产的的套套数数，并并与与上上

24、限限比比较较，大大于于则则输输出出上上限限值值并并退退出出，否否则则再再调调用用动动态态规规划划；同同时时，在在运运行行动动态态规规划划的的过过程程中中，也也可可以以每每完完成成一一阶阶段段工工作作便便与与上上限限值值进进行行比比较较，这这样样以以来来，便便可可望望在在动动态态规规划划完完成成前前提提前前结束程序。其算法设计为：结束程序。其算法设计为：uuS1S1：读入数据。：读入数据。uuS2S2：贪心求上限并计算出一可行解，判断是否需进行下一步。：贪心求上限并计算出一可行解，判断是否需进行下一步。uuS3S3：动态规划求解。：动态规划求解。uuS4S4：输出。：输出。贪心优化uu显然，对每

25、条流水线，我们没有必要将对每个时刻都进行动态规划，可以拿出大部分时间进行成套生产，剩下一些时间进行动态规划uu这样，显然可以极大的减少动态规划的状态总数，从而节约动态规划的计算时间。例7：Hoteluu有有N N个男人，个男人，MM个女人，其中有个女人，其中有C C对夫妇要住房。对夫妇要住房。现在有现在有P P个房子。每个房子有个费用个房子。每个房子有个费用CiCi和床位和床位BiBi。住房有以下要求住房有以下要求:uu1.1.每个房子住的人数不能超过每个房子住的人数不能超过BiBiuu2.2.一个房间住了夫妇，不能再住其他人。一个房间住了夫妇，不能再住其他人。uu3.3.不考虑夫妇情况下：一

26、个房间住了男人后，不不考虑夫妇情况下：一个房间住了男人后，不能再住女人。对女人也是一样。能再住女人。对女人也是一样。uu问最少的费用。问最少的费用。(n500,m500,P500,Bi=5)(n500,m500,P500,Bisize,lsize)(ksize,lsize)，那么肯定，那么肯定uu无论如何无论如何Ci/BiCi/Bi最小的那些房间肯定会被选到。最小的那些房间肯定会被选到。uu于是我们可以贪心在于是我们可以贪心在ksize,lsizeksize,lsize的时候，给他的时候，给他们安排们安排Ci/BiCi/Bi最小的房间。最小的房间。uu然后再进行动态规划。然后再进行动态规划。u

27、u由于由于Bi=5.Bi=5.所以所以size=20size=20就够了。就够了。uu这样时间复杂度就很低了。这样时间复杂度就很低了。方法4：利用恰当的数据结构存储状态，减少状态查找时间uu例例6 6、LOSTCITYLOSTCITYuu现给出一张单词表、特定的语法规则和一篇文章：现给出一张单词表、特定的语法规则和一篇文章：uu文章和单词表中只含文章和单词表中只含2626个小写英文字母个小写英文字母azaz。uu单词表中的单词只有名词，动词和辅词这三种词性，且相单词表中的单词只有名词，动词和辅词这三种词性，且相同词性的单词互不相同。单词的个数不超过同词性的单词互不相同。单词的个数不超过1000

28、1000，单词的，单词的长度均不超过长度均不超过2020。uu语法规则可简述为：名词短语：任意个辅词前缀接上一个语法规则可简述为：名词短语：任意个辅词前缀接上一个名词；动词短语：任意个辅词前缀接上一个动词；句子：名词；动词短语：任意个辅词前缀接上一个动词；句子：以名词短语开头，名词短语与动词短语相间连接而成。以名词短语开头，名词短语与动词短语相间连接而成。uu文章的长度不超过文章的长度不超过5k5k。且已知文章是由有限个句子组成的，。且已知文章是由有限个句子组成的，句子只包含有限个单词。句子只包含有限个单词。uu编程将这篇文章划分成最少的句子，在此前提之下，要求编程将这篇文章划分成最少的句子，

29、在此前提之下，要求划分出的单词数最少。划分出的单词数最少。我们分别用v,u,a表示动词，名词和辅词，给出的文章用L1.M表示，则状态表示描述为：F(v,i)：表示将L的前i个字符划分为以动词结尾（当iM时，可带任意个辅词后缀）的最优分解方案下划分的句子数与单词数；F(u,i)：表示将L的前i个字符划分为以名词结尾（当iM时，可带任意个辅词后缀）的最优分解方案下划分的句子数与单词数。状态转移方程为：F(v,i)=minF(u,j)+(0,1)，L(j+1.i)为动词；F(v,j)+(0,1)，L(j+1.i)为辅词，iM；F(u,i)=minF(u,j)+(1,1),L(j+1.i)为名词；F(

30、v,j)+(0,1),L(j+1.i)为名词；F(u,j)+(0,1),L(j+1.i)为辅词，iM；边界条件：F(v,0)=(1,0)；F(u,0)=(,)；问题的解为：minF(v,M),F(u,M)；顺序查找顺序查找 二分查找二分查找哈希表哈希表检索树检索树算法的时间算法的时间复杂度复杂度O(20*M*O(20*M*N)N)O(20*M*logO(20*M*log2 2N)N)O(20*MO(20*M)O(M)O(M)最坏情况下最坏情况下的比较次数的比较次数10108 810106 610105 55*105*103 3Input.009Input.009超时超时1.27s1.27s0.

31、32s0.32s0.05s0.05sInput.010Input.010超时超时1.33s1.33s0.33s0.33s0.05s0.05s采用不同的方法查找字符串的比较：设单词表的规模为N（N的最大值为1000）设文章的长度为M（M的最大值为5000）方法5：利用四边形不等式的性质降维uu例8：邮局uu按照递增顺序给出一条直线上坐标互不相同的n个村庄，要求从中选择p个村庄建立邮局，每个村庄使用离它最近的那个邮局，使得所有村庄到各自所使用的邮局的距离总和最小。uu试编程计算最小距离和，以及邮局建立方案。分析uu将n个村庄按坐标递增依次编号为1.n，第i个邮局的坐标为di，wi,j表示在di,j

32、之间建立一个邮局的最小距离和。uu设mi,j表示在前j个村庄建立i个邮局的最小距离和。分析uu可以证明，当仅建立一个邮局时，最优解出现在中位数，即设建立邮局的村庄为k u同时，令同时，令si,j=k，记录使用前，记录使用前i-1个邮局的村庄数，便于在个邮局的村庄数，便于在算出最小距离和之后构造最优建立方案。算出最小距离和之后构造最优建立方案。u上述算法中上述算法中wi,j可通过可通过O(n)时间的预处理，在时间的预处理，在O(1)的时间的时间内算出，所以，该算法的状态总数为内算出，所以，该算法的状态总数为O(n*p)，每个状态转移的，每个状态转移的状态数为状态数为O(n)，每次状态转移的时间为

33、，每次状态转移的时间为O(1)，该算法总的时间，该算法总的时间复杂度为复杂度为O(p*n2)。猜想uuWW满足四边形不等式，即满足四边形不等式，即uu证明：证明：uu设设y=(i+j)/2,z=(i+j)/2,y=(i+j)/2,z=(i+j)/2,下面分为两种情形，下面分为两种情形，zyzy或或zyzy，下面仅讨论，下面仅讨论zyzy，zyzy的情况是类似的。的情况是类似的。uu由由izyjizyj有：有：证明uu用数学归纳法证明函数用数学归纳法证明函数用数学归纳法证明函数用数学归纳法证明函数mm也满足四边形不等式。对四边形也满足四边形不等式。对四边形也满足四边形不等式。对四边形也满足四边形

34、不等式。对四边形不等式中不等式中不等式中不等式中“长度长度长度长度”l=j-i”l=j-i进行归纳：进行归纳：进行归纳：进行归纳：uu当当当当i=ii=i或或或或j=jj=j时，不等式显然成立。由此可知，当时，不等式显然成立。由此可知，当时，不等式显然成立。由此可知，当时，不等式显然成立。由此可知，当l1l1时，时，时，时，函数函数函数函数mm满足四边形不等式。满足四边形不等式。满足四边形不等式。满足四边形不等式。uu下面分两种情形进行归纳证明：下面分两种情形进行归纳证明：下面分两种情形进行归纳证明：下面分两种情形进行归纳证明：情形情形情形情形1 1：ii=jjii=jjkj。下面只讨论。下面

35、只讨论。下面只讨论。下面只讨论kjkj，kjkj的情况的情况的情况的情况是类似的。是类似的。是类似的。是类似的。uu情形情形2 2：iijjiijyzy。uu情形情形2.12.1，当，当zyjjzyjj时：时：情形情形2.22.2，当，当i-1i-1yzji-1i-1yzj时：时：uu令令令令si,j=ksi,j=k，(ij)(ij)，最后，我们证明决策，最后，我们证明决策，最后，我们证明决策，最后，我们证明决策si,jsi,j满足单调性。满足单调性。满足单调性。满足单调性。uu令令令令mki,j=mi-1,k+wk+1,jmki,j=mi-1,k+wk+1,j；uu我们先来证明我们先来证明我

36、们先来证明我们先来证明si-1,jsi,jsi-1,jsi,j，只要证明对于所有，只要证明对于所有，只要证明对于所有，只要证明对于所有ikkjikkj且且且且mki-1,jmki-1,jmki-1,jmki-1,j，有：，有：，有：，有：mki,jmki,jmki,jmki,j。uu类似地，我们可以证明一个更强的不等式类似地，我们可以证明一个更强的不等式类似地，我们可以证明一个更强的不等式类似地，我们可以证明一个更强的不等式 mki-1,j-mki-1,jmki,j-mki,j mki-1,j-mki-1,jmki,j-mki,j mki-1,j+mki,jmki,j+mki-1,j mki-

37、1,j+mki,jmki,j+mki-1,juu利用递推定义式展开整理的：利用递推定义式展开整理的：利用递推定义式展开整理的：利用递推定义式展开整理的：mi-2,k+mi-1,kmi-mi-2,k+mi-1,kmi-1,k+mi-2,k1,k+mi-2,k，这就是，这就是，这就是，这就是i-2i-1kki-2i-1kk时时时时mm的四边形不等式。的四边形不等式。的四边形不等式。的四边形不等式。uu我们再来证明我们再来证明我们再来证明我们再来证明si,jsi,j+1si,jsi,j+1，设设设设kkjkkj，则我们只需证明一个更强的不等式：，则我们只需证明一个更强的不等式：，则我们只需证明一个更

38、强的不等式：，则我们只需证明一个更强的不等式：mki,j-mki,jmki,j+1-mki,j+1 mki,j-mki,jmki,j+1-mki,j+1uu也就是也就是也就是也就是mki,j+mki,j+1mki,j+1+mki,jmki,j+mki,j+1mki,j+1+mki,juu利用递推定义式展开整理的：利用递推定义式展开整理的：利用递推定义式展开整理的：利用递推定义式展开整理的：wk+1,j+wk+1,j+1wk+1,j+1+wk+1,jwk+1,j+wk+1,j+1wk+1,j+1+wk+1,j，这就是这就是这就是这就是k+1k+1jj+1k+1k+1jj+1时时时时ww的四边形不等式。的四边形不等式。的四边形不等式。的四边形不等式。uu综上所述，该问题的决策综上所述，该问题的决策综上所述，该问题的决策综上所述，该问题的决策si,jsi,j具有单调性，因此具有单调性，因此具有单调性，因此具有单调性，因此uu优化后的算法时间复杂度为优化后的算法时间复杂度为优化后的算法时间复杂度为优化后的算法时间复杂度为O(n*p)O(n*p)。