动态规划基础(1)

动态规划的基础(1)线性，区间，矩阵清华大学莫涛提纲动态规划简介例题分析线性模型：例题1~4区间模型：例题5~8矩阵模型：例题9~12状态压缩模型：思考题4,5带权有向的多段图问题•给定一个带权的有向图，要求从点A到点D的最短路径。•设F(i)表示从点A到达点i的最短距离，则有•F(A)=0•F(B1)=5,F(B2)=2•F(C1)=min{F(B1)+3}=8•F(C2)=min{F(B1)+2,F(B2)+7}=7•F(C3)=min{F(B2)+4}=6•F(D)=min{F(C1)+4,F(C2)+3,F(C3)+5}=10多阶段最优化决策问题由上例可以看出，整个问题分成了A、B、C、D四个阶段来做，每个阶段的数值的计算只会跟上一个阶段的数值相关，这样一直递推下去直到目标。即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线。状态转移方程•设fk(i)—k阶段状态i的最优权值，即初始状态至状态i的最优代价。fk+1(i)=min{fk(j)+u(i,j)}第k+1阶段状态第k阶段状态决策动态规划的基本原理最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。无后效性原则给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。线性动态规划问题•最典型的特征就是状态都在一条线上，并且位置固定，问题一般都规定只能从前往后取状态，解决的办法是根据前面的状态特征，选取最优状态作为决策进行转移。•设前i个点的最优值，研究前i-1个点与前i个点的最优值，•利用第i个点决策转移，如下图。•状态转移方程一般可写成:fi(k)=min{fi-1orj(k’)+u(i,j)oru(i,i-1)}例题一.拦截导弹•给定N个数–求最长的不上升子序列长度–求最少有多少个不上升序列能覆盖所有的数，即求最少覆盖序列。•N=10000.分析•设f(i)表示前i个数的最长不上升序列的长度。则,f(i)=max{f(j)+1},其中jianda[j]=a[i]这里0ji=n。显然时间复杂度为O(n2)。•上述式子的含义：找到i之前的某j，这个数不比第i个数小,对于所有的j取f(j)的最大值。优化•分析样例•这里找j,是在1~i之间进行寻找，那么我们能否快速查找到我们所要更改的j呢?•要能更改需要两个条件：–jianda[j]=a[i]–f(j)尽可能大•以上两个条件提示我们后面的值一定要小于等于前面的值。因此我们试着构建一个下降的序列。在这个下降的序列中查找可以更改的f值,使得序列的值尽可能大。i1234567838920715530029917015865f12323456•具体过程：i1234567838920715530029917015865第1次389第2次389207第3次389207155第4次389300155（由于207300389,因此更新）第5次389300299（由于155299300,因此更新）第6次389300299170第7次389300299170158第8次38930029917015865思考？•有些同学可能会问:–对于每个f,为什么只保留一个数值呢?–而对于该序列，为什么要保留较大的值呢？1.再回过头来看方程:f(i)=max{f(j)+1},其中jianda[j]=a[i]该式子表示找前面的一个最大f的符合条件的j,因此只要保存符合条件的最大的j就可以了。2.在f值相同的情况下，保留较大的数显然更好。因为后面的数若能跟较小的数构成下降序列也一定能能较大的数构成下降序列，反之则不一定。例如207与300的f=2,但207不能与299构成下降序列，而300则可以。3.因为生成的序列为有序序列，因此我们可以采用二分查找的方法很快查找到更新的值，时间复杂度为O(n㏒n)求导弹的最小覆盖•第二问很容易想到贪心法：那就是采取多次求最长不上升序列的办法，然后得出总次数。•上述贪心法不正确，很容易就能举出反例。例如：“7541632”用多次求最长不上升序列所有为“75432”、“1”、“6”共3套系统；但其实只要2套，分别为：“7541”与“632”。•那么，正确的做法又是什么呢？分析•上述问题的原因是若干次最优决策值和不一定能推导出整个问题的最优。•为了解决这个问题下面介绍一个重要性质：–最少链划分=最长反链长度•为了证明这个性质，需要了解离散数学中偏序集的相关概念和性质以及偏序集的Dilworth定理。解决•结论：–最少多少套系统=最长导弹高度上升序列长度–构造方法：将f[i]相等的数放在一个不上升序列–见样例分析•算法法与最长不上升序列类似•时间复杂度O(n㏒n)例题二.合唱队形•给定一个包含n个整数的序列A，找出其最长的一个先递增再递减的子序列•例如{1,6,4,7,3,5,2,8}中最好的解时{1,4,7,5,2}•N=100000解法分析•考虑中间那个数（即最大数），前面是递增序列，后面是递减序列，且两部分之间没有影响•F[i]表示以前i个数，以第i个数结尾的最长上升子序列的长度•F[i]=max{F[j]+1}(ji，A[j]A[i])•同理可以求出G[i]表示第i个数后面的最长下降子序列的长度•答案=Max{F[i]+G[i]-1}例题三.青蛙过河•在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。•题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。【输入文件】•输入文件river.in的第一行有一个正整数L（1=L=109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1=S=T=10，1=M=100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。【输出文件】•输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。【样例输入】1023523567【样例输出】2【数据规模】对于30%的数据，L=10000；对于全部的数据，L=109。分析•由于不能往回跳，很容易想到用动态规划解决这个题目。•设f(i)表示跳到第i个点需要踩到的最少石子数，则很容易写出动态规划的状态转移方程:1)}-Tf(L1),...,f(Lmin{f(L),AnsiT)k(S1k)}-{f(iiT)k(Sk)}-{f(imin)(0)0(点有石子第点没有石子第iff•时间复杂度是O(L*(T-S))，但本题的L高达109，根本无法承受!进一步分析•我们先来考虑这样一个问题：长度为k的一段没有石子的独木桥，判断是否存在一种跳法从一端正好跳到另一端。•若ST，事实上对于某个可跳步长区间[S,T]，必然存在一个MaxK使得任何k=MaxK，都可以从一端正好跳到另一端。•题设中1=S=T=10，经过简单推导或者程序验证就可以发现，取MaxK=100就能满足所有区间。于是我们可以分两种情况讨论：1.S=T时：这时候由于每一步只能按固定步长跳，所以若第i个位置上有石子并且imodS=0那么这个石子就一定要被踩到。这是我们只需要统计石子的位置中哪些是S的倍数即可。复杂度O(M)2.ST时：首先我们作如下处理：若存在某两个相邻石子之间的空白区域长度MaxK+2*T，我们就将这段区域缩短成长度为MaxK+2*T。可以证明处理之后的最优值和原先的最优值相同。ab如上图所示，白色点表示连续的一长段长度大于MaxK+2*T的空地，黑色点表示石子。设原先的最优解中，白色段的第一个被跳到的位置a，最后一个被跳到的位置是b，则在做压缩处理之后，a和b的距离仍然大于MaxK，由上面的结论可知，必存在一种跳法从a正好跳到b，而且不经过任何石子。•所以原来的最优解必然在处理之后的最优解解集中。•经过这样的压缩处理，独木桥的长度L’最多为(M+1)*(MaxK+2*T)+M，大约12000左右。压缩之后再用先前的动态规划求解，复杂度就简化成了O(L’*(T-S))，已经可以在时限内出解了。•这样本题就得到了解决。例题四.最长公共子序列•给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列i0，i1，…，ik-1，使得对所有的j=0，1，…，k-1，有xij=yj。•例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。•给出两个字串S1和S2，长度不超过5000.•求这两个串的最长公共子串长度。分析样例S1=“ABCBDAB.”S2=“BABCBD.”•可以看出他们的最长公共子串有ABCB,ABCD,BCBD等，长度为4.•从样例分析，我们思考的方式为要找出S1串与S2串的公共子串，假设将S1固定，从第1个位置开始直到最后一个位置为止，与S2的各个部分不断找最长公共子串•当然S1也可以变化，这样我们即得出了思路:–枚举S1的位置i–枚举S2的位置j–找出S1的前i位与S2的前j位的最长公共子串，直到两个串的最后一个位置为止。动态规划•设f(i,j)表示S的前i位与T的前j位的最长公共子串长度。则有，•时间复杂度O(n*m)jijitsjijiftsjijifjifjijif&&0,,1)1,1(&&0,)},,1(),1,(max{0||0,0),(当当当主程序框架n:=length(a);m:=length(b);fori:=1tonbeginforj:=1tomdobeginf[j]:=max(f[j-1],pf[j]);{从前面的状态直接转移过来}if(a[i]=b[j])and(pf[j-1]+1f[j])then{多增加一位的情况}f[j]:=pf[j-1]+1;end;pf:=f;end;说明：pf是一个与f完全相同的数组，实现f(i)与f(i-1)的滚动样例运行过程S=“ABCBDAB.”T=“BABCBD.”初始：f(i,0)=0,f(0,i)=0;∵S[1]≠T[1];∴f(1,1)=MAX{f(1,0),f(0,1)}=0∵S[1]=T[2];∴f(1,2)=MAX{f(1,0)+1}=1∵S[2]=T[1];∴f(2,1)=MAX{f(1,0)+1}=1∵S[2]≠T[2];∴f(2,2)=MAX{f(1,2),f(2,1)}=1∵S[2]=T[3];∴f(2,3)=MAX{f(1,2)+1}=2∵S[3]≠T[1];∴f(3,1)=MAX{f(3,0),f(2,1)}=1∵S[3]≠T[2];∴f(3,2)=MAX{f(2,2),f(3,1)}=1∵S[3]≠T[3];∴f(3,3)=MAX{f(3,2),f(2,3)}=2……一直求到f(8,7),ans=f(8,7)-1；减1是因为最后都有一个”.”区间动态规划问题•该类问题的基本特征是能将问题分解成为两两合并的形式。解决方法是对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题的最优值。有点类似分治的