《DP-线型动态规划.ppt》由会员分享，可在线阅读，更多相关《DP-线型动态规划.ppt（42页珍藏版）》请在金锄头文库上搜索。
1、线型动态规划线型动态规划长沙市雅礼中学长沙市雅礼中学朱全民朱全民带权有向的多段图问题带权有向的多段图问题给定一个带权的有向图，要求从点A到点D的最短路径。设F(i)表示从点A到达点i的最短距离，则有F(A)=0F(B1)=5,F(B2)=2F(C1)=minF(B1)+3=8F(C2)=minF(B1)+2,F(B2)+7=7F(C3)=minF(B2)+4=6F(D)=minF(C1)+4,F(C2)+3,F(C3)+5=10多阶段最优化决策问题多阶段最优化决策问题l由由上上例例可可以以看看出出，整整个个问问题题分分成成了了A、B、C、D四四个个阶阶段段来来做做，每每个个阶阶段段的的数数值值
2、的的计计算算只只会会跟跟上上一一个阶段的数值相关，这样一直递推下去直到目标。个阶段的数值相关，这样一直递推下去直到目标。l即即由由初初始始状状态态开开始始，通通过过对对中中间间阶阶段段决决策策的的选选择择，达达到到结结束束状状态态。这这些些决决策策形形成成了了一一个个决决策策序序列列，同时确定了完成整个过程的一条最优的活动路线同时确定了完成整个过程的一条最优的活动路线。状态转移方程状态转移方程设设fk(i)k阶段状态i的最优权值，即初始状态至状态i的最优代价。 fk+1(i) = min fk(j) + u(i,j) 第k+1阶 段状态 第k阶段状态决策动态规划的基本原理动态规划的基本原理l最
3、优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。l无后效性原则给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。第第1题：关键子工程题：关键子工程l有有N个子工程，每一个子工程都有一个完成个子工程，每一个子工程都有一个完成时间。时间。l子工程之间的有一些依赖关系，即某些子子工程之间的有一些依赖关系，即某些子工程必须在一些子工程完成之后才开工。工程必须在一些子工程完成之后才开工。l在满足子
4、工程间的依赖关系前提下，可以在满足子工程间的依赖关系前提下，可以有任何多个子工程同时在施工。有任何多个子工程同时在施工。l求整个工程的完成的最短时间。求整个工程的完成的最短时间。l求出所有关键子工程。求出所有关键子工程。lN200有向图的关键路径分析l如果该图能够进行拓扑排序，证明有解，反之则如果该图能够进行拓扑排序，证明有解，反之则无解。无解。l根据拓扑序列进行动态规划求解，得到工程所需根据拓扑序列进行动态规划求解，得到工程所需的完成时间。的完成时间。设设FI表示完成子工程表示完成子工程I所需的最早时间。所需的最早时间。动态规划方程：动态规划方程：FI=MAXFJ+AI，Jl根据的得到的根据
5、的得到的F序列和拓扑序列，查找关键工程。序列和拓扑序列，查找关键工程。初始时，最后完成的一个或多个工程为关键工程。初始时，最后完成的一个或多个工程为关键工程。如果如果FI=FJ-AI，J，且第，且第I个子工程为关键工程，个子工程为关键工程，那么第那么第J个子工程也是关键工程。个子工程也是关键工程。l时间复杂度为时间复杂度为O(N2)。拦截导弹给定给定N个数个数求最长的不上升子序列长度求最长的不上升子序列长度求最少有多少个不上升序列能覆盖所有的数，求最少有多少个不上升序列能覆盖所有的数，即求最少覆盖序列。即求最少覆盖序列。N=10000.分析设设f(i)表示前表示前i个数的最长不上升序列的长度。
6、个数的最长不上升序列的长度。则则,f(i)=maxf(j)+1,其中其中j=ai这里这里0ji=n。显然时间复杂度为显然时间复杂度为O(n2)。上述式子的含义：找到上述式子的含义：找到i之前的某之前的某j，这个数，这个数不比第不比第i个数小个数小,对于所有的对于所有的j取取f(j)的最大值。的最大值。优化分析样例分析样例这里找这里找j,是在是在1i之间进行寻找，那么我们能否快速查找到之间进行寻找，那么我们能否快速查找到我们所要更改的我们所要更改的j呢呢?要能更改需要两个条件：要能更改需要两个条件：j=aif(j)尽可能大尽可能大以上两个条件提示我们后面的值一定要小于等于前面的值。以上两个条件提
7、示我们后面的值一定要小于等于前面的值。因此我们试着构建一个下降的序列。在这个下降的序列中因此我们试着构建一个下降的序列。在这个下降的序列中查找可以更改的查找可以更改的f值值,使得序列的值尽可能大。使得序列的值尽可能大。i12345678389 207 155 300 299 170 15865f12323456具体过程：i1234567838920715530029917015865第第1次次389第第2次次389207第第3次次389207155第第4次次389300155（由于（由于207300389,因此更新）因此更新）第第5次次389300299（由于（由于155299300,因此更新
8、）因此更新）第第6次次389300299170第第7次次389300299170158第第8次次38930029917015865思考？有些同学可能会问有些同学可能会问:对于每个对于每个f,为什么只保留一个数值呢为什么只保留一个数值呢?而对于该序列，为什么要保留较大的值呢？而对于该序列，为什么要保留较大的值呢？1. 再回过头来看方程再回过头来看方程:f(i)=maxf(j)+1,其中其中j=ai该式子表示找前面的一个最大该式子表示找前面的一个最大f的符合条件的的符合条件的j,因此只要保因此只要保存符合条件的最大的存符合条件的最大的j就可以了。就可以了。2.2.在在f值相同的情况下，保留较大的数
9、显然更好。因为后面值相同的情况下，保留较大的数显然更好。因为后面的数若能跟较小的数构成下降序列也一定能能较大的数的数若能跟较小的数构成下降序列也一定能能较大的数构成下降序列，反之则不一定。例如构成下降序列，反之则不一定。例如207与与300的的f=2,但但207不能与不能与299构成下降序列，而构成下降序列，而300则可以。则可以。3.3.因为生成的序列为有序序列，因此我们可以采用二分查因为生成的序列为有序序列，因此我们可以采用二分查找的方法很快查找到更新的值，时间复杂度为找的方法很快查找到更新的值，时间复杂度为O(nn)求导弹的最小覆盖第二问很容易想到贪心法：那就是采取多次求最长不上升序列的
10、办法，然后得出总次数。上述贪心法不正确，很容易就能举出反例。例如： “7 5 4 1 6 3 2”用多次求最长不上升序列所有为“7 5 4 3 2”、“1”、“6”共3套系统；但其实只要2套，分别为： “7 5 4 1”与“6 3 2”。那么，正确的做法又是什么呢？ 分析上述问题的原因是若干次最优决策值和不上述问题的原因是若干次最优决策值和不一定能推导出整个问题的最优。一定能推导出整个问题的最优。为了解决这个问题下面介绍一个重要性质：为了解决这个问题下面介绍一个重要性质：最少链划分最少链划分=最长反链长度最长反链长度为了证明这个性质，需要了解离散数学中为了证明这个性质，需要了解离散数学中偏序集
11、的相关概念和性质以及偏序集的偏序集的相关概念和性质以及偏序集的Dilworth定理。定理。偏序集偏序是在集合偏序是在集合X上的二元关系上的二元关系（这只是个抽象符号，不（这只是个抽象符号，不是是“小于或等于小于或等于”），它满足自反性、反对称性和传递性。），它满足自反性、反对称性和传递性。即，对于即，对于X中的任意元素中的任意元素a,b和和c，有，有:自反性：自反性：aa;反对称性：如果反对称性：如果ab且且ba，则有，则有a=b;传递性：如果传递性：如果ab且且bc，则，则ac。带有偏序关系的集合称为偏序集。带有偏序关系的集合称为偏序集。令令(X,)是一个偏序集，对于集合中的两个元素是一个偏
12、序集，对于集合中的两个元素a、b，如果，如果有有ab或者或者ba，则称，则称a和和b是可比的，否则是可比的，否则a和和b不可比。不可比。一个反链一个反链A是是X的一个子集，它的任意两个元素都不能进行的一个子集，它的任意两个元素都不能进行比较。比较。一个链一个链C是是X的一个子集，它的任意两个元素都可比。的一个子集，它的任意两个元素都可比。定理在在X中，对于元素中，对于元素a，如果任意元素，如果任意元素b，都有，都有ab，则称则称a为极小元。为极小元。定理定理1：令（：令（X,）是一个有限偏序集，并令）是一个有限偏序集，并令r是其是其最大链的大小。则最大链的大小。则X可以被划分成可以被划分成r个
13、但不能再少个但不能再少的反链。的反链。其对偶定理称为其对偶定理称为Dilworth定理：定理：令（令（X,）是一个有限偏序集，并令）是一个有限偏序集，并令m是反链的最是反链的最大的大小。则大的大小。则X可以被划分成可以被划分成m个但不能再少的链。个但不能再少的链。虽然这两个定理内容相似，但第一个定理证明要虽然这两个定理内容相似，但第一个定理证明要简单一些。此处就只证明定理简单一些。此处就只证明定理1。证明：设证明：设p为最少反链个数为最少反链个数(1)先证明先证明X不能划分成小于不能划分成小于r个反链。由于个反链。由于r是最大是最大链链C的大小，的大小，C中任两个元素都可比，因此中任两个元素都
14、可比，因此C中任中任两个元素都不能属于同一反链。所以两个元素都不能属于同一反链。所以p=r。(2)设设X1X，A1是是X1中的极小元的集合。从中的极小元的集合。从X1中删中删除除A1得到得到X2。注意到对于。注意到对于X2中任意元素中任意元素a2，必存，必存在在X1中的元素中的元素a1，使得，使得a1=a2。令。令A2是是X2中极小中极小元的集合，从元的集合，从X2中删除中删除A2得到得到X3，最终会有，最终会有一个一个Xk非空而非空而Xk+1为空。于是为空。于是A1,A2,Ak就是就是X的的反链的划分，同时存在链反链的划分，同时存在链a1=a2=k。由于。由于X被划分成了被划分成了k个反链，
15、因此个反链，因此r=k=p。(3)因此因此r=p，定理，定理1得证。得证。解决解决要求最少的覆盖，按照要求最少的覆盖，按照Dilworth定理定理最少链划分最少链划分 =最长反链长度最长反链长度所以最少多少套系统所以最少多少套系统 =最长导弹高度上升最长导弹高度上升序列长度。序列长度。知道了怎样求最长不上升算法，同样也就知道了怎样求最长不上升算法，同样也就知道了怎样求最长上升序列。知道了怎样求最长上升序列。时间复杂度时间复杂度O(nn)。青蛙过河青蛙过河(NOIP2005)在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一
16、些石子，青蛙很讨厌踩在这些石跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：整点：0，1，L（其中（其中L是桥的长度）。坐标为是桥的长度）。坐标为0的点的点表示桥的起点，坐标为表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到到T之间的任意正整数（包括之间的任意正
17、整数（包括S,T）。当青蛙跳到或跳过坐）。当青蛙跳到或跳过坐标为标为L的点时，就算青蛙已经跳出了独木桥。的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度题目给出独木桥的长度L，青蛙跳跃的距离范围，青蛙跳跃的距离范围S,T，桥上，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。到的石子数。【输入文件输入文件】输入文件输入文件river.in的第一行有一个正整数的第一行有一个正整数L（1=L=109），），表示独木桥的长度。第二行有三个正整数表示独木桥的长度。第二行有三个正整数S，T，M，分别，分别表示青蛙一次跳跃的最小距离
18、，最大距离，及桥上石子的表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中个数，其中1=S=T=10，1=M=100。第三行有。第三行有M个不同的正整数分别表示这个不同的正整数分别表示这M个石子在数轴上的位置（数个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。间用一个空格隔开。【输出文件输出文件】输出文件输出文件river.out只包括一个整数，表示青蛙过河最少需只包括一个整数，表示青蛙过河最少需要踩到的石子数。要踩到的石子数。【样例输入样例输入】1023523567【样例输出样例输出】2【
19、数据规模数据规模】对于对于30%的数据，的数据，L=10000；对于全部的数据，对于全部的数据，L=109。 分析 由于不能往回跳，很容易想到用动态规划解决这个题目。由于不能往回跳，很容易想到用动态规划解决这个题目。设设f(i)表示跳到第表示跳到第i个点需要踩到的最少石子数，则很容易写个点需要踩到的最少石子数，则很容易写出动态规划的状态转移方程出动态规划的状态转移方程:时间复杂度是时间复杂度是O(L*(T-S)，但本题的，但本题的L高达高达109，根本无法，根本无法承受承受! 进一步分析我们先来考虑这样一个问题：长度为我们先来考虑这样一个问题：长度为k的一段没有的一段没有石子的独木桥，判断是否
20、存在一种跳法从一端正好石子的独木桥，判断是否存在一种跳法从一端正好跳到另一端。跳到另一端。若若S=MaxK，都可以从一端，都可以从一端正好跳到另一端。正好跳到另一端。题设中题设中1=S=T=10，经过简单推导或者程序验证，经过简单推导或者程序验证就可以发现，取就可以发现，取MaxK=100就能满足所有区间。就能满足所有区间。 于是我们可以分两种情况讨论：于是我们可以分两种情况讨论：1.S=T时：时：这时候由于每一步只能按固定步长跳，所以若第这时候由于每一步只能按固定步长跳，所以若第i个位置上个位置上有石子并且有石子并且imodS=0那么这个石子就一定要被踩到。这是那么这个石子就一定要被踩到。这
21、是我们只需要统计石子的位置中哪些是我们只需要统计石子的位置中哪些是S的倍数即可。复杂度的倍数即可。复杂度O(M)2.SMaxK+2*T，我们就将这段区域缩短成长度为，我们就将这段区域缩短成长度为MaxK+2*T。可以证明处理之后的最优值和原先的最优值相。可以证明处理之后的最优值和原先的最优值相同。同。ab如上图所示，白色点表示连续的一长段长度大于如上图所示，白色点表示连续的一长段长度大于MaxK+2*T的空地，黑色点表示石子。设原先的最优解中，白色段的第的空地，黑色点表示石子。设原先的最优解中，白色段的第一个被跳到的位置一个被跳到的位置a，最后一个被跳到的位置是，最后一个被跳到的位置是b，则在
22、做压，则在做压缩处理之后，缩处理之后，a和和b的距离仍然大于的距离仍然大于MaxK，由上面的结论可知，由上面的结论可知，必存在一种跳法从必存在一种跳法从a正好跳到正好跳到b，而且不经过任何石子。，而且不经过任何石子。所以原来的最优解必然在处理之后的最优解所以原来的最优解必然在处理之后的最优解解集中。解集中。经过这样的压缩处理，独木桥的长度经过这样的压缩处理，独木桥的长度L最多为最多为(M+1)*(MaxK+2*T)+M，大约，大约12000左右。压左右。压缩之后再用先前的动态规划求解，复杂度就缩之后再用先前的动态规划求解，复杂度就简化成了简化成了O(L*(T-S)，已经可以在时限内出解，已经可
23、以在时限内出解了。了。这样本题就得到了解决。这样本题就得到了解决。火车进站火车进站给定给定N辆火车辆火车第第i辆火车的进站时间辆火车的进站时间arrive(i)第第i辆火车的离站时间辆火车的离站时间leave(i)车站只能容纳车站只能容纳M辆火车辆火车求最多能接受多少辆火车？求最多能接受多少辆火车？M=3l先看样先看样1.1.第第1，2，3辆分别进入（辆分别进入（123）；）；2.2.第第2辆离开，可以看出要离开时，被第辆离开，可以看出要离开时，被第1辆火车卡在前面，因此第辆火车卡在前面，因此第1辆辆火车不能进入，队列为（火车不能进入，队列为（23）3.3.第第2辆离开，第辆离开，第4辆进入（
24、辆进入（34）4.4.第第3，4辆离开，队列空辆离开，队列空5.5.第第5，6辆进入辆进入 （56）6.6.第第5，6分别离开，队列空分别离开，队列空l因此答案为因此答案为5辆辆分析按到达时间排序和离开时间排序，这样每一辆火按到达时间排序和离开时间排序，这样每一辆火车用线段描述，有：车用线段描述，有：排在前面的火车，其进站时间必须先于排在后排在前面的火车，其进站时间必须先于排在后面的火车；面的火车；排在前面的火车，其出站时间必须先于排在后排在前面的火车，其出站时间必须先于排在后面的火车，否则该列火车就要先进后出，不满面的火车，否则该列火车就要先进后出，不满足队列特点。足队列特点。这样对于任一列
25、排序后的火车这样对于任一列排序后的火车i，只有排在其后的，只有排在其后的火车才有可能在它出站之后进站。接下来的任务火车才有可能在它出站之后进站。接下来的任务便是采用动态规划方法求解了。便是采用动态规划方法求解了。m=1时时设设fi表示第表示第i列火车进站时，其后的火车列火车进站时，其后的火车最多可以进站的数量，最多可以进站的数量， 则有：则有：fj=maxfi+1，（满足，（满足i比比j先进站，先进站，且且j在在i出站之后进站）；出站之后进站）；m=2设设fi,j表示车站停靠表示车站停靠i,j两列火车两列火车(ij)时，其后的时，其后的火车（包括火车（包括i,j本身）最多可以进站的数量本身）最
26、多可以进站的数量,则则:fj,k=maxfi,j+1条件：必须满足按条件：必须满足按i,j,k顺序进站和出站，另外还顺序进站和出站，另外还要满足要满足k在在i出站后进站。出站后进站。m=3设设fi,j,k表示车站停靠表示车站停靠i,j,k三列火车三列火车(ijk)时，其后时，其后的火车（包括的火车（包括i,j,k）最多可以进站的数量。则有，）最多可以进站的数量。则有，fj,k,l=maxfi,j,k+1条件：必须满足按条件：必须满足按i,j,k,l顺序进站和出站，另外还顺序进站和出站，另外还要满足要满足l在在i出站后进站。出站后进站。求最长公共子序列求最长公共子序列给定的字符序列给定的字符序列
27、X=“x0，x1，xm-1”，序列序列Y=“y0，y1，yk-1”是是X的子序列，存在的子序列，存在X的一个严格递增的一个严格递增下标序列下标序列，使得对所有的，使得对所有的j=0，1，k-1，有，有xij=yj。例如，例如，X=“ABCBDAB”，Y=“BCDB”是是X的一个子序的一个子序列。列。给出两个字串给出两个字串S1和和S2，长度不超过，长度不超过5000.求这两个串的最长公共子串长度。求这两个串的最长公共子串长度。分析样例S1=“ABCBDAB.”S2=“BABCBD.”可以看出他们的最长公共子串有可以看出他们的最长公共子串有ABCB,ABCD,BCBD等，长等，长度为度为4.从样
28、例分析，我们思考的方式为要找出从样例分析，我们思考的方式为要找出S1串与串与S2串的公共串的公共子串，假设将子串，假设将S1固定，从第固定，从第1个位置开始直到最后一个位个位置开始直到最后一个位置为止，与置为止，与S2的各个部分不断找最长公共子串的各个部分不断找最长公共子串当然当然S1也可以变化，这样我们即得出了思路也可以变化，这样我们即得出了思路:枚举枚举S1的位置的位置i枚举枚举S2的位置的位置j找出找出S1的前的前i位与位与S2的前的前j位的最长公共子串，直到两个位的最长公共子串，直到两个串的最后一个位置为止。串的最后一个位置为止。动态规划设设f(i,j)表示表示S的前的前i位与位与T的
29、前的前j位的最长公共子串长度。则位的最长公共子串长度。则有，有，时间复杂度时间复杂度O(n*m)主程序框架n:=length(a);m:=length(b);for i:=1 to n begin for j:=1 to m do begin fj:=max(fj-1,pfj); 从前面的状态直接转移过来 if (ai=bj) and (pfj-1+1fj) then 多增加一位的情况 fj:=pfj-1+1; end; pf:=f; end;说明：pf是一个与f完全相同的数组，实现f(i)与f(i-1)的滚动样例运行过程S=“ABCBDAB.”T=“BABCBD.”初始：初始：f(i,0)=
30、0,f(0,i)=0; S1T1; f(1,1)=MAXf(1,0),f(0,1)=0 S1=T2; f(1,2)=MAXf(1,0)+1=1 S2=T1; f(2,1)=MAXf(1,0)+1=1 S2T2; f(2,2)=MAXf(1,2),f(2,1)=1 S2=T3; f(2,3)=MAXf(1,2)+1=2 S3T1; f(3,1)=MAXf(3,0),f(2,1)=1 S3T2; f(3,2)=MAXf(2,2),f(3,1)=1 S3T3; f(3,3)=MAXf(3,2),f(2,3)=2一直求到一直求到f(8,7),ans=f(8,7)-1；减；减1是因为最后都有一个是因为最
31、后都有一个”.”最短回文串最短回文串如果一个字符串正过来读和倒过来读是一样的，那如果一个字符串正过来读和倒过来读是一样的，那么这个字符串就被称作回文串。么这个字符串就被称作回文串。例如例如abcdcba，abcddcba就是回文串，而就是回文串，而abcdabcd不是。不是。任务：对于任意一个字符串，输出将这个字符串变任务：对于任意一个字符串，输出将这个字符串变为回文串需要插入的最少字符个数，比如，为回文串需要插入的最少字符个数，比如，ab3bd只需要插入只需要插入2个字符就可以变为一个回文串个字符就可以变为一个回文串.0n=1992，n为字符串长度。为字符串长度。分析ab3bd只需变为只需变
32、为adb3bda即可，在前面插入即可，在前面插入d，在，在后面插入后面插入a;我们分几种情况讨论：我们分几种情况讨论：若若A形如形如 ?A?，(问号代表任意一个相同字符，问号代表任意一个相同字符，下同下同)则只需将则只需将A变为回文串。变为回文串。若若A形如形如?A再在再在A的后面插入一个的后面插入一个”?”若若A形如形如A?再在再在A的前面插入一个的前面插入一个”?”动态规划设设f(i,j)为将为将Ai.Aj变为回文串的最小代价，则变为回文串的最小代价，则一共有一共有n2个状态，状态转移是个状态，状态转移是O(1)的，总的复杂度的，总的复杂度为为O(n2)主程序： fi,j表示把i到j这一段
33、变成回文需要最少添加多少字符for i:=n downto 1 do for j:=i+1 to n do begin if si=sj then 不用添加 fi,j:=fi+1,j-1 else fi,j:=maxint; if fi,j-1+1fi,j then 添加一个 fi,j:=fi,j-1+1; 前插1个字符 if fi+1,j+1fi,j then fi,j:=fi+1,j+1; 后插1个字符 end;总结总结线型动态规划问题，最典型的特征就是状态都在一条线上，线型动态规划问题，最典型的特征就是状态都在一条线上，并且位置固定，问题一般都规定只能从前往后取状态，解并且位置固定，问题一般都规定只能从前往后取状态，解决的办法是根据前面的状态特征，选取最优状态作为决策决的办法是根据前面的状态特征，选取最优状态作为决策进行转移。进行转移。设前设前i个点的最优值，研究前个点的最优值，研究前i-1个点与前个点与前i个点的最优值，个点的最优值，利用第利用第i个点决策转移，如下图。个点决策转移，如下图。状态转移方程一般可写成状态转移方程一般可写成: f fi i(k)=minfi-1i-1 or jor j(k)+u(i,j)oru(i,i-1)
