动态规划步骤.pptVIP

　　动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。　　根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下： 标准动态规划的基本框架1. 对fn+1(xn+1)初始化; {边界条件}2. for k:=n downto 1 do3. for 每一个xk∈Xk do4. for 每一个uk∈Uk(xk) dobegin 5. fk(xk):=一个极值; {∞或－∞} 6. xk+1:=Tk(xk,uk); {状态转移方程} 7. t:=φ(fk+1(xk+1),vk(xk,uk)); {基本方程(9)式} 8. if t 比fk(xk)更优 then fk(xk):=t; {计算fk(xk)的最优值}end;9. t:=一个极值; {∞或－∞}10. for 每一个x1∈X1 do11. if f1(x1)比t 更优 then t:=f1(x1); {按照10 式求出最优指标}12. 输出t; 但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：1. 分析最优解的性质，并刻划其结构特征。2. 递归地定义最优值。3. 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。4. 根据计算最优值时得到的信息，构造一个最优解。步骤(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位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 【输入文件】 输入文件chorus.in的第一行是一个整数N（2 ≤ N ≤ 100），表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti（130 ≤ Ti ≤ 230）是第i位同学的身高（厘米）。 【输出文件】 输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。 【样例输入】 8 186 186 150 200 160 130 197 220 【样例输出】 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减去合唱队人数即为解。 出列人数最少，也就是说留的人最多，也就是序列最长。 这样分析就是典型的最长下降子序列问题。只要枚举每一个人站中间时可以的到的最优解。显然它就等于，包括他在内向左求最长上升子序列，向右求最长下降子序列。 我们看一下复杂度： 计算最长下降子序列的复杂度是O（N2），一共求N次，总复杂度是O（N3）。这样的复杂度对于这个题的数据范围来说是可以AC的。但有没有更好的方法呢？ 其实最长子序列只要一次就可以了。因为最长下降（上升）子序列不受中间人的影响。 只要用OPT1求一次最长上升子序列，OPT2求