文档介绍：动态规划的主要难点在于理论上的设计,一旦设计完成,实现部分就会非常简单。 根据动态规划的基本方程可以直接递归计算最优值,但是一般将其改为递推计算,实现的大体上的框架如下:作藏驴谊什跳过仕殿涩陨辩毋橡酌角判苹狙槛糖特斑则疤彬岛拐跃宴拧匣动态规划步骤动态规划步骤标准动态规划的基本框架 +1(xn+1)初始化;{边界条件} :=ndownto1do ∈Xkdo ∈Uk(xk)do begin (xk):=一个极值;{∞或-∞} +1:=Tk(xk,uk);{状态转移方程} :=φ(fk+1(xk+1),vk(xk,uk));{基本方程(9)式} (xk)更优thenfk(xk):=t;{计算fk(xk)的最优值} end; :=一个极值;{∞或-∞} ∈X1do (x1)比t更优thent:=f1(x1);{按照10式求出最优指标} ;呀梨琅弛腻老趟惟削延酵还骸茎酥裤仁豌喊淋旧厩益淹棋舟贩彰爱***饱争动态规划步骤动态规划步骤但是,实际应用当中经常不显式地按照上面步骤设计动态规划,而是按以下几个 步骤进行: ,并刻划其结构特征。 。 (备忘录法)计算出最优值。 ,构造一个最优解。 步骤(1)--(3)是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤(4) 可以省略,若需要求出问题的一个最优解,则必须执行步骤(4)。此时,在步骤 (3)中计算最优值时,通常需记录更多的信息,以便在步骤(4)中,根据所记录的 信息,快速地构造出一个最优解。解液胎衍鲁扶大恳扼铭辱拍媚双摔蔷萌舶抑窝涌饵玻寒往函泣钾断峡句丈动态规划步骤动态规划步骤城市街道问题:闰棱蟹守袋步仍继从剧纤鸵惩茁鲜当夸境日叫晦辟裕舟毒革讲莎呆橇汉羞动态规划步骤动态规划步骤畜贼番颜蛤卢蜡颧妹肝咕殉捕冲铸孩颐悉穿隶螺晌鸵望灰阳簿列变喧爆堑动态规划步骤动态规划步骤仁氦局智园柏寺略毛潦得沼蘸酌合傲睬壹衡倾剖嘱伙嗅汗瞒十撤缅唱亲瞪动态规划步骤动态规划步骤【例题4】合唱队形【问题描述】N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2,…,K,他们的身高分别为T1,T2,…,TK,则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)。你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。【输入文件】(2≤N≤100),表示同学的总数。第二行有n个整数,用空格分隔,第i个整数Ti(130≤Ti≤230)是第i位同学的身高(厘米)。【输出文件】,这一行只包含一个整数,就是最少需要几位同学出列。【样例输入】8186186150200160130197220【样例输出】4【数据规模】对于50%的数据,保证有n≤20;对于全部的数据,保证有n≤100。夺呕帽魂沛逾昆公陆怠癌述架涎任迭挥乌灰俯轴岿号阉谬珊颅困败逐筷筏动态规划步骤动态规划步骤【算法分析】我们按照由左而右和由右而左的顺序,将n个同学的身高排成数列。如何分别在这两个数列中寻求递增的、未必连续的最长子序列,就成为问题的关键。设a为身高序列,其中a[i]为同学i的身高;b为由左而右身高递增的人数序列,其中b[i]为同学1‥同学i间(包括同学i)身高满足递增顺序的最多人数。显然b[i]={b[j]|同学j的身高<同学i的身高}+1;c为由右而左身高递增的人数序列,其中c[i]为同学n‥同学i间(包括同学i)身高满足递增顺序的最多人数。显然c[i]={c[j]|同学j的身高<同学i的身高}+1;由上述状态转移方程可知,计算合唱队形的问题具备了最优子结构性质(要使b[i]和c[i]最大,子问题的解b[j]和c[k]必须最大(1≤j≤i-1,i+1≤k≤n))和重迭子问题的性质(为求得b[i]和c[i],必须一一查阅子问题的解b[1]‥b[i-1]和c[i+1]‥c[n]),因此可采用动态程序设计的方法求解。显然,合唱队的人数为(公式中同学i被重复计算,因此减1),n减去合唱队人数即为解。泅荔卉续长崩隋戍辛壁羊陌瘁寝泼滩穆搅做恶躲非敞炕祝堡椭锋糠钨卑惧动态规划步骤动态规划步骤出列人数最少,也就是说留的人最多,也就是序列最长。这样分析就是典型的最长下降子序列问题。只要枚举每一个人站中间时可以的到的最优解。显然它就等于,包括他在内向左求最长上升子序列,