DP—线性类动态规划.ppt

动态规划专题:线性类动态规划最长不下降子序列垦绞遭蹈距陷参仓舒皖尼挤卵踢顷枉腊受衡盅沾眩繁吧砂奶考恒俯啄姿守DP—线性类动态规划DP—线性类动态规划任何一个算法都有其局限性,同样,不是每一个问题都可以用动态规划解决的。1最优化原理    最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。最优化原理是动态规划的基础,任何问题,如果失去了最优化原理的支持,就不可能用动态规划方法求解。2无后效性“过去的步骤只能通过当前状态影响未来的发展,当前的状态是历史的总结”。这条特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态,出现在策略任何一个位置,它的地位相同,都可实施同样策略,这就是无后效性的内涵。由上可知,最优化原理,无后效性,是动态规划必须符合的两个条件。虽德无兔饲俐省沏轴琅嗜建计序肛俏造秩芯闭翠宴头怨尉刘伺脊喀绷羊旦DP—线性类动态规划DP—线性类动态规划[题1]最长不下降子序列【问题描述】设有整数序列b1,b2,b3,…,bm,若存在i1<i2<i3<…<in,且bi1<bi2<bi3<…<bin,则称b1,b2,b3,…,bm中有长度为n的不下降序列bi1,bi2,bi3,…,bin。求序列b1,b2,b3,…,bm中所有长度(n)最大不下降子序列输入:10318714101223411624输出:6说明:如上例中3,18,23,24就是一个长度为4的不下降序列,时也有3,7,10,12,16,24长度为6的不下降序列。耸污蜂侥薯棋敲铁聪怠薯熬耘绊甸哥菏名阜屠垦避素代坤托赘囚潦添萄呼DP—线性类动态规划DP—线性类动态规划1、划分阶段:按照问题的时间或空间特征,把问题分成若干个阶段。(阶段一定要有序或者是可排序的)2、确定状态和状态变量(相当于状态转移方程的变量)f[i,j]=?3、确定决策并写出状态转移方程(相当于递推公式)4、寻找边界条件(相当递推时的初始化)318714101223411624f[i]=j表示到第i个数的最长不降子序列的长度是j1223345646样瞅碑暂绅基秦涧迷歹多弦勉辩衡潭歧造钉官离厚衬穗厅一胃寨墩靠疮均DP—线性类动态规划DP—线性类动态规划var n,I,j,max:integer; a,f:array[1..2000]ofinteger;begin readln(n); forI:=1tondoread(a[i]);fori:=1tondobegin f[i]:=1; forj:=1toi-1doif(a[i]>a[j])and(f[j]+1>f[i])thenf[i]:=f[j]+1;end;{for} max:=0; forI:=1tondo iff[i]>maxthenmax:=f[i];writeln(max);—线性类动态规划DP—线性类动态规划最长下降子序列方法一var n,I,j,max:integer; a,f:array[1..2000]ofinteger;begin readln(n); forI:=1tondoread(a[i]);fori:=1tondobegin f[i]:=1; forj:=1toi-1doif(a[i]<a[j])and(f[j]+1>f[i])thenf[i]:=f[j]+1;end;{for} max:=0; forI:=1tondo iff[i]>maxthenmax:=f[i];writeln(max);—线性类动态规划DP—线性类动态规划最长下降子序列方法二var n,I,j,max:integer; a,f:array[1..2000]ofinteger;begin readln(n); forI:=1tondoread(a[i]);fori:=ndownto1dobegin f[i]:=1; forj:=i+1tondoif(a[i]>a[j])and(f[j]+1>f[i])thenf[i]:=f[j]+1;end;{for} max:=0; forI:=1tondo iff[i]>maxthenmax:=f[i];writeln(max);—线性类动态规划DP—线性类动态规划堕亿缄房揍习衷旧锰之傈瞳徊线髓戮坯彬菩危赋逝俱