最小路径得分=6 状态表示 1-2
用二元组D（X，Y）描述问题，D（X，Y）表示到 达第X层第Y个位置时的得分，那么 D（X，Y）的 最优解包含了子问题D（X-1，Y）或D（X-1，Y-1） 的最优解，状态转移方程为 D（X，Y）= Min {D （X-1，Y），D（X-1，Y-1）} + A[X，Y]
11
动态规划算法求解问题的一般思路
S1:K=4，有：F4(D1)=3，F4(D2)=4，F4(D3)=3 S2: K=3，有： F3(C1)=min{d3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2)}=min{8,10}=8 F3(C2)=d3(C2,D1)+f4(D1)=5+3=8 F3(C3)=d3(C3,D3)+f4(D3)=8+3=11 F3(C4)=d3(C4,D3)+f4(D3)=3+3=6 S3: K=2，有： F2(B1)=min{d2(B1,C1)+F3(C1),d2(B1,C2)+f3(C2),d2(B1,C3)+F3(C3 )}=min{9,12,14}=9 F2(B2)=min{d2(B2,c2)+F3(C2),d2(B2,C4)+F3(C4)}=min{16,10}=10 S4：k=1，有： F1(A)=min{d1(A,B1)+F2(B1),d1(A,B2)+F2(B2)}=min{14,13}=13 因此由A点到E点的全过程的最短路径为A—>B2一>C4—>D3—>E。 最短路程长度为13。
18
4.2动态规划算法的基本要素
三、备忘录方法
•备忘录方法的控制结构与直接递归方法的控制 结构相同，区别在于备忘录方法为每个解过的子 问题建立了备忘录以备需要时查看，避免了相同 子问题的重复求解。 •步骤：
为每个问题建立一个记录项，初值设为一个特殊值（表 未求解）
每个待求解子问题，首先查记录项，有解答则直接选取， 否则求解该子问题。
最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优 化原理的支持，就不可能用动态规划方法计算。能采用动态规划求解 的问题都需要满足一定的条件： (1) 问题中的状态必须满足最优化原理； (2) 问题中的状态必须满足无后效性。
所谓的无后效性是指：“下一时刻的状态只与当前状态有关，而和当 前状态之前的状态无关，当前的状态是对以往决策的总结”。
D（1，1）= A[1,1]
9
动态规划算法求解问题的一般思路
【例题1】最短路径问题。图中给出了一个地图，
地图中每个顶点代表一个城市，两个城市间的连 线代表道路，连线上的数值代表道路的长度。现 在，想从城市A到达城市E，怎样走路程最短，最 短路程的长度是多少?
10
动态规划算法求解问题的一般思路
【分析】把从A到E的全过程分成四个阶段，用k表 示阶段变量，第1阶段有一个初始状态A，两条可供 选择的支路ABl、AB2；第2阶段有两个初始状态 B1、 B2，B1有三条可供选择的支路，B2有两条可供 选择的支路……。 用dk(xk，xk+1)表示在第k阶段由初始状态xk到下阶段 的初始状态xk+1的路径距离，Fk(xk)表示从第k阶段的 xk到终点E的最短距离，利用倒推方法求解A到E的 最短距离。
7
4.1算法总体思想
动态规划设计一般要经历以下几个步骤：
1、划分阶段：按照问题的时间或空间特征，把问题分为若 干个阶段。 2、确定状态：将问题发展到各个阶段时所处的各种客观情 况用不同的状态表示出来。 3、确定决策并写出状态转移方程：因为决策和状态转移有 着天然的联系，状态转移就是根据上一阶段的状态和决策来 导出本阶段的状态，所以如果确定了决策，状态转移方程也 就可以写出。 4、寻找边界条件：给出的状态转移方程是一个递推式，需 要一个递推的终止条件或边界条件。 5、程序设计实现：动态规划的主要难点在于理论上的设计， 一旦设计完成，实现部分就会非常简单。
【样例输入】8 186 186 150 200 160 130 197 220 【样例输出】 4 【说明】该样例中，可以要队头身高186的两个人出列,
以及队尾197和220的人出列,共4人出列,所以输出4.
20
4.3 典型问题-合唱队形
【算法分析】 ：先分别从左到右求最大上升子序列，从右到 左求最大下降子序列，再枚举中间最高的一个人。算法时间 复杂度O(N2)。 【思路】：数组a[i]是第i个人的身高，b[i]是从左边第一个到 a[i]的最长上升子序列，c[i]是从右边第一个到a[i]的最长上升 子序列。
12
动态规划算法求解问题的一ห้องสมุดไป่ตู้思路
每个阶段中，都求出本阶段的各个初始状态到过 程终点E的最短路径和最短距离，当逆序倒推到过 程起点A时，便得到了全过程的最短路径及最短距 离，同时附带得到了一组最优结果(即各阶段的各 状态到终点E的最优结果)。
13
[思考与练习]：若城市路径示意图如图所示，图 中，每条边上的数字是这段道路的长度。条件： 从A地出发，只允许向右或向上走。试寻找一条 从A地到B地的最短路径和长度。
5
4.1算法总体思想
适合于用动态规划法求解的问题具有以下特点： 1、可以划分成若干个阶段，问题的求解过程就是对若干个
阶段的一系列决策过程。 2、每个阶段有若干个可能状态 3、一个决策将你从一个阶段的一种状态带到下一个阶段的
某种状态。 4、在任一个阶段，最佳的决策序列和该阶段以前的决策无
关。 5、各阶段状态之间的转换有明确定义的费用，而且在选择
16
4.2 动态规划算法的基本要素
一、最优子结构
•某个问题的最优解包含着其子问题的最优解。这种性质称为最 优子结构性质。
例如图中，若路线I和J是A到C的最优路径， 则根据最优化原理，路线J必是从B到C的 最优路线。这可用反证法证明：假设有另 一路径J‘是B到C的最优路径，则A到C的 路线取I和J’比I和J更优，矛盾。从而证明 J‘必是B到C的最优路径。 最优子结构是问题能用动态规划算法求解 的前提。
2
4.1算法总体思想
动态规划法的定义：在求解问题中，对于每一 步决策，列出各种可能的局部解，再依据某种 判定条件，舍弃那些肯定不能得到最优解的局 部解，在每一步都经过筛选，以每一步都是最 优解来保证全局是最优解。
动态规划通常应用于最优化问题，即做出一组 选择以达到一个最优解。关键是存储子问题的 每一个解，以备它重复出现。
3
4.1算法总体思想
动态规划算法与分治法类似，其基本思想也是 将待求解问题分解成若干个子问题。
但是经分解得到的子问题往往不是互相独立的。 不同子问题的数目常常只有多项式量级。在用 分治法求解时，有些子问题被重复计算了许多 次。
4
4.1算法总体思想
1、阶段：把问题分成几个相互联系的有顺序的几 个环节，这些环节即称为阶段。 2、状态：某一阶段的出发位置称为状态。 3、决策：从某阶段的一个状态演变到下一个阶段 某状态的选择。 4、状态转移方程：前一阶段的终点就是后一阶段 的起点，前一阶段的决策选择导出了后一阶段的状 态，这种关系描述了由k阶段到k+1阶段状态的演变 规律，称为状态转移方程。
1
最优化原理
1951年美国数学家R．Bellman等人，根据一类多阶段问题的特点，把 多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以 解决。与此同时，他提出了解决这类问题的“最优化原 理”(Principle of Optimality)。
“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题， 需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的， 对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的 最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1， Dk+2，…，Dn也是最优的。
第4章 动态规划 学习要点: dynamic programming
• 理解动态规划算法的概念。 • 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 • 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。
最佳决策时有递推关系（即动态转移方程）。
6
4.1算法总体思想
动态规划与一般搜索技术最大不同的地方就是记录了已 求解过的问题的结果。这里包含了两个方面的内容 ：子 问题的记录和子问题结果的记录。其中，子问题的记录是 最重要，也是最为复杂的，它就是通常我们所说的状态表 示。 通常我们用一个数、一组数或一个向量来实现状态 表示。 状态表示要满足两个要求：正确、合理描述子问题和描 述的 子问题满足最优子结构性质；从算法实现角度来看， 状态表示必须能够用基本数据 结构实现并且能满足空间 要求。
不管a[i]为什么值时，b[i]>=1;（因为它本身就是一个上升 序列元素。）假设 i=1 ，此时b[1]=1;因为a[1]的前面没有元素。 那么如果a[2]>a[1]，显然可以得到b[2]=b[1]+1,因为a[1]、a[2] 是一个上升子序列。如果a[2]<=a[1]，那么b[2]只能为1。同理， 若a[3]>a[1]..a[3-1]，则b[3]=max{b[1]...b[3-1]}+1。由此我们 可以得到递推关系式： b[i]=max{b[j](1<=j<i)|a[i]> a[j]}+1 c[i]=max{c[j](i<=j<N)|a[i]> a[j]}+1 然后，可以得到符合合唱队的队列是b[i]+c[i]-1(a[i]被重复计 算了一次)，而题目要求的合唱队列是：max{b[i]+c[i]-1}。