DP—线性类动态规划.ppt

1、动态规划专题：线性类动态规划,最长不下降子序列,任何一个算法都有其局限性，同样，不是每一个问题都可以用动态规划解决的。 1 最优化原理最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。 最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法求解。 2 无后效性 “过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结”。这条特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策略任何一个位置，它的地位相同

2、，都可实施同样策略，这就是无后效性的内涵。 由上可知，最优化原理，无后效性，是动态规划必须符合的两个条件。,题1 最长不下降子序列,【问题描述】 设有整数序列b1,b2,b3,bm，若存在i1i2i3in，且bi1bi2bi3bin，则称 b1,b2,b3,bm中有长度为n的不下降序列bi1,bi2,bi3,bin。求序列b1,b2,b3,bm中所有长度(n)最大不下降子序列 输入：10 3 18 7 14 10 12 23 41 16 24 输出：6 说明：如上例中3，18，23，24就是一个长度为4的不下降序列，时也有3，7，10，12，16，24长度为6的不下降序列。,1、划分阶段：按照

3、问题的时间或空间特征，把问题分成若干个阶段。 （阶段一定要有序或者是可排序的）,2、确定状态和状态变量（相当于状态转移方程的变量）fi,j=?,3、确定决策并写出状态转移方程（相当于递推公式）,4、寻找边界条件(相当递推时的初始化),3 18 7 14 10 12 23 41 16 24,fi=j 表示到第i个数的最长不降子序列的长度是 j,1,2,2,3,3,4,5,6,4,6,var n,I,j,max:integer; a,f:array1.2000 of integer; begin readln(n); for I:=1 to n do read(ai); for i:=1 to n

4、 do begin fi:=1; for j:=1 to i-1 do if (aiaj)and(fj+1fi) then fi:=fj+1; end; for max:=0; for I:=1 to n do if fimax then max:=fi; writeln(max); end.,i,1,i,a,f,2,i,2,i,3,i,3,最长下降子序列方法一,var n,I,j,max:integer; a,f:array1.2000 of integer; begin readln(n); for I:=1 to n do read(ai); for i:=1 to n do begin

5、 fi:=1; for j:=1 to i-1 do if (aifi) then fi:=fj+1; end; for max:=0; for I:=1 to n do if fimax then max:=fi; writeln(max); end.,i,1,i,a,f,1,i,2,i,3,i,4,i,2,最长下降子序列方法二,var n,I,j,max:integer; a,f:array1.2000 of integer; begin readln(n); for I:=1 to n do read(ai); for i:=n downto 1 do begin fi:=1; for j:=i+1 to n do if (aiaj)and(fj+1fi) then fi:=fj+1; end; for max:=0; for I:=1 to n do if fimax then max:=fi; writeln(max); end.,i,1,i,a,f,1,i,2,i,3,i,4,i,4,线性动态规划： 线性动态规划一般都是以长度来划分阶段，具体长度是指区间长度还是前I个数，要具体问题具体分析 例1：Vijos1369难解的问题，最长升序列，从K前和K后分别动态规