动态规划基础讲解及案例分析解答课件

1、动态规划基础讲解及案例分析解答1第九课动态规划动态规划( (I) )综合实践考核动态规划基础讲解及案例分析解答数字三角形 1、问题描述、问题描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。路径上的数字之和。注意：路径上的每一步只能从一个数走到下一层上和它最近的注意：路径上的每一步只能从一个数走到下一

2、层上和它最近的左边的数或者右边的数。左边的数或者右边的数。动态规划基础讲解及案例分析解答问题描述输入数据输入数据输入的第一行是一个整数输入的第一行是一个整数N (1 N = 100)，给出，给出三角形的行数。下面的三角形的行数。下面的N 行给出数字三角形。数字三行给出数字三角形。数字三角形上的数的范围都在角形上的数的范围都在0 和和100 之间。之间。输出要求输出要求输出最大的和。输出最大的和。动态规划基础讲解及案例分析解答问题描述输入样例输入样例573 88 1 02 7 4 44 5 2 6 5输出样例输出样例30动态规划基础讲解及案例分析解答2、解题思路 这道题目可以用递归的方法解决。基

3、本思路是：这道题目可以用递归的方法解决。基本思路是：以以D( r, j)表示第表示第r 行第行第 j 个数字个数字(r，j 都从都从1 开始算开始算)，以，以MaxSum(r, j) 代表从第代表从第 r 行的第行的第 j 个数字到底边的最佳路径个数字到底边的最佳路径的数字之和，则本题是要求的数字之和，则本题是要求 MaxSum(1, 1) 。从某个从某个D(r, j)出发，显然下一步只能走出发，显然下一步只能走D(r+1, j)或者或者D(r+1, j+1)。如果走。如果走D(r+1, j)，那么得到的，那么得到的MaxSum(r, j)就是就是MaxSum(r+1, j) + D(r, j

4、)；如果走；如果走D(r+1, j+1)，那么得，那么得到的到的MaxSum(r, j)就是就是MaxSum(r+1, j+1) + D(r, j)。所。所以，选择往哪里走，就看以，选择往哪里走，就看MaxSum(r+1, j)和和MaxSum(r+1, j+1)哪个更大了。哪个更大了。动态规划基础讲解及案例分析解答3、参考程序 I#include #define MAX_NUM 100int DMAX_NUM + 10MAX_NUM + 10;int N;int MaxSum( int r, int j)if( r = N )return Drj;int nSum1 = MaxSum(r+1

5、, j);int nSum2 = MaxSum(r+1, j+1);if( nSum1 nSum2 )return nSum1+Drj;return nSum2+Drj; 动态规划基础讲解及案例分析解答3、参考程序 Iint main(void)int m;scanf(%d, &N);for( int i = 1; i = N; i + )for( int j = 1; j = i; j + )scanf(%d, &Dij);printf(%d, MaxSum(1, 1);return 0;提交结果：提交结果：Time Limit Exceed动态规划基础讲解及案例分析解答程序

6、I分析 上面的程序，效率非常低，在上面的程序，效率非常低，在N 值并不大，值并不大，比如比如N=100 的时候，就慢得几乎永远算不出的时候，就慢得几乎永远算不出结果了。结果了。为什么会这样呢？是因为过多的重复计算。为什么会这样呢？是因为过多的重复计算。我们不妨将对我们不妨将对MaxSum 函数的一次调用称为函数的一次调用称为一次计算。那么，每次计算一次计算。那么，每次计算MaxSum(r, j)的的时候，都要计算一次时候，都要计算一次MaxSum(r+1, j+1)，而每次计算而每次计算MaxSum(r, j+1)的时候，也要的时候，也要计算一次计算一次MaxSum(r+1, j+1)。重复计

7、算因。重复计算因此产生。此产生。在 题 目 中 给 出 的 例 子 里 ， 如 果 我 们 将在 题 目 中 给 出 的 例 子 里 ， 如 果 我 们 将MaxSum(r, j)被计算的次数都写在位置（被计算的次数都写在位置（r, j），那么就能得到右面的三角形：），那么就能得到右面的三角形：11 11 2 11 3 3 11 4 6 4 173 88 1 02 7 4 44 5 2 6 5动态规划基础讲解及案例分析解答程序分析 n 从上图可以看出，最后一行的计算次数总和是从上图可以看出，最后一行的计算次数总和是16，倒数第二行，倒数第二行的计算次数总和是的计算次数总和是8。不难总结出规律，

8、对于。不难总结出规律，对于N 行的三角形，总行的三角形，总的计算次数是的计算次数是20 +21+22+2(N-1)=2N-1。当。当N= 100 时，总的计算次数是一个让人无法接受的大数字。时，总的计算次数是一个让人无法接受的大数字。n 既然问题出在重复计算，那么解决的办法，当然就是，一个值既然问题出在重复计算，那么解决的办法，当然就是，一个值一旦算出来，就要记住，以后不必重新计算。即第一次算出一旦算出来，就要记住，以后不必重新计算。即第一次算出MaxSum(r, j)的值时，就将该值存放起来，下次再需要计算的值时，就将该值存放起来，下次再需要计算MaxSum(r, j)时，直接取用存好的值即

9、可，不必再次调用时，直接取用存好的值即可，不必再次调用MaxSum 进行函数递归计算了。这样，每个进行函数递归计算了。这样，每个MaxSum(r, j)都只都只需要计算需要计算1 次即可，那么总的计算次数（即调用次即可，那么总的计算次数（即调用MaxSum 函数的函数的次数）就是三角形中的数字总数，即次数）就是三角形中的数字总数，即1+2+3+N = N(N+1)/2。n 如何存放计算出来的如何存放计算出来的MaxSum（r, j）值呢？显然，用一个二维）值呢？显然，用一个二维数组数组aMaxSumNN就能解决。就能解决。aMaxSumrj就存放就存放MaxSum(r, j)的计算结果。下次再

10、需要的计算结果。下次再需要MaxSum(r, j)的值时，的值时，不必再调用不必再调用MaxSum 函数，只需直接取函数，只需直接取aMaxSumrj的值即的值即可。可。动态规划基础讲解及案例分析解答4、参考程序 II#include #include #define MAX_NUM 100int DMAX_NUM + 10MAX_NUM + 10;int N;int aMaxSumMAX_NUM + 10MAX_NUM + 10;int MaxSum( int r, int j) if( r = N ) return Drj; if( aMaxSumr+1j = -1 ) /如果如果MaxS

11、um(r+1, j)没有计算过没有计算过 aMaxSumr+1j = MaxSum(r+1, j); if( aMaxSumr+1j+1 = -1) aMaxSumr+1j+1 = MaxSum(r+1, j+1); if( aMaxSumr+1j aMaxSumr+1j+1 ) return aMaxSumr+1j +Drj; return aMaxSumr+1j+1 + Drj;动态规划基础讲解及案例分析解答4、参考程序 IIint main(void) int m; scanf(%d, & N); /将将 aMaxSum 全部置成全部置成-1, 开始时所有的开始时所有的 MaxS

12、um(r, j)都没有算过都没有算过 memset(aMaxSum, -1, sizeof(aMaxSum); for( int i = 1; i = N; i + ) for( int j = 1; j = i; j + ) scanf(%d, & Dij); printf(%d, MaxSum(1, 1); return 0;动态规划基础讲解及案例分析解答程序II分析 这种将一个问题分解为子问题递归求解，并且将中间结果这种将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做保存以避免重复计算的办法，就叫做“动态规划动态规划”。动态规动态规划通常用来求最优解

13、，能用动态规划解决的求最优解问题，划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。必须满足，最优解的每个局部解也都是最优的。以上题为例，以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。字出发到达到底部的最佳路径。实际上，递归的思想在编程时未必要实现为递归函数。在上实际上，递归的思想在编程时未必要实现为递归函数。在上面的例子里，有递推公式：面的例子里，有递推公式： Drj rNaMaxSumrjMax(aMaxSumr1j, aMaxSumr1j1)Drj

14、 其其他他因此，不需要写递归函数，从因此，不需要写递归函数，从aMaxSumN-1这一行元素这一行元素开始向上逐行递推，就能求得开始向上逐行递推，就能求得aMaxSum11的值了。的值了。动态规划基础讲解及案例分析解答5、参考程序 IIIint DMAX_NUM + 10MAX_NUM + 10;int N;int aMaxSumMAX_NUM + 10MAX_NUM + 10;int main(void) int i, j; scanf(%d, & N); for( i = 1; i = N; i + ) for( j = 1; j = i; j + ) scanf(%d, &

15、;Dij); for( j = 1; j 1 ; i - ) for( j = 1; j aMaxSumij+1 ) aMaxSumi-1j = aMaxSumij + Di-1j; else aMaxSumi-1j = aMaxSumij+1 + Di-1j; printf(%d, aMaxSum11); return 0;思考题思考题：上面的几个程序：上面的几个程序只算出了最佳路径的数字只算出了最佳路径的数字之和。如果要求输出最佳之和。如果要求输出最佳路径上的每个数字，该怎路径上的每个数字，该怎么办？么办？动态规划基础讲解及案例分析解答动态规划解题的一般思路 n 许多求最优解的问题可以用动

16、态规划来解决。许多求最优解的问题可以用动态规划来解决。n 首先要把原问题分解为若干个子问题。注意单纯的递归往往会导首先要把原问题分解为若干个子问题。注意单纯的递归往往会导致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就要被保存，所以每个子问题只需求解一次。要被保存，所以每个子问题只需求解一次。 n 子问题经常和原问题形式相似，有时甚至完全一样，只不过规模子问题经常和原问题形式相似，有时甚至完全一样，只不过规模从原来的从原来的n 变成了变成了n-1，或从原来的，或从原来的nm 变成了变成了n(m-1) 等等等。等。n 找到子问题

17、，就意味着找到了将整个问题逐渐分解的办法。找到子问题，就意味着找到了将整个问题逐渐分解的办法。n 分解下去，直到最底层规模最小的的子问题可以一目了然地看出分解下去，直到最底层规模最小的的子问题可以一目了然地看出解。解。n 每一层子问题的解决，会导致上一层子问题的解决，逐层向上，每一层子问题的解决，会导致上一层子问题的解决，逐层向上，就会导致最终整个问题的解决。就会导致最终整个问题的解决。n 如果从最底层的子问题开始，自底向上地推导出一个个子问题的如果从最底层的子问题开始，自底向上地推导出一个个子问题的解，那么编程的时候就不需要写递归函数。解，那么编程的时候就不需要写递归函数。动态规划基础讲解及

18、案例分析解答动态规划解题的一般思路 n 用动态规划解题时，将和子问题相关的各个变量的一组取值，用动态规划解题时，将和子问题相关的各个变量的一组取值，称之为一个称之为一个“状态状态”。一个。一个“状态状态”对应于一个或多个子问题，对应于一个或多个子问题，所谓某个所谓某个“状态状态”下的下的“值值”，就是这个，就是这个“状态状态”所对应的子所对应的子问题的解。问题的解。n 比如数字三角形，子问题就是比如数字三角形，子问题就是“从位于从位于(r，j)数字开始，到数字开始，到底边路径的最大和底边路径的最大和”。这个子问题和两个变量。这个子问题和两个变量r 和和j 相关，那相关，那么一个么一个“状态状态

19、”，就是，就是r, j 的一组取值，即每个数字的位置就的一组取值，即每个数字的位置就是一个是一个“状态状态”。该。该“状态状态”所对应的所对应的“值值”，就是从该位置，就是从该位置的数字开始，到底边的最佳路径上的数字之和。的数字开始，到底边的最佳路径上的数字之和。n 定义出什么是定义出什么是“状态状态”，以及在该，以及在该 “状态状态”下的下的“值值”后，后，就要找出不同的状态之间如何迁移就要找出不同的状态之间如何迁移即如何从一个或多个即如何从一个或多个“值值”已知的已知的 “状态状态”，求出另一个，求出另一个“状态状态”的的“值值”。状。状态的迁移可以用递推公式表示，此递推公式也可被称作态的

20、迁移可以用递推公式表示，此递推公式也可被称作“状态状态转移方程转移方程”。动态规划基础讲解及案例分析解答动态规划解题的一般思路 n用动态规划解题，如何寻找用动态规划解题，如何寻找“子问题子问题”，定义，定义“状态状态”，“状态转移方程状态转移方程”是什么样的，并没有一定之规，需要具体问是什么样的，并没有一定之规，需要具体问题具体分析，题目做多了就会有感觉。题具体分析，题目做多了就会有感觉。n甚至，对于同一个问题，分解成子问题的办法可能不止一种，甚至，对于同一个问题，分解成子问题的办法可能不止一种，因而因而“状态状态”也可以有不同的定义方法。不同的也可以有不同的定义方法。不同的“状态状态”定义定

21、义方法可能会导致时间、空间效率上的区别。方法可能会导致时间、空间效率上的区别。 Drj rNaMaxSumrjMax(aMaxSumr1j, aMaxSumr1j1)Drj 其其他他动态规划基础讲解及案例分析解答最长上升子序列 1、问题描述、问题描述 一个数的序列一个数的序列bi，当，当b1 b2 . bS 的时候，的时候，我们称这个序列是上升的。对于给定的一个序列我们称这个序列是上升的。对于给定的一个序列(a1, a2, ., aN)，我们可以得到一些上升的子序列，我们可以得到一些上升的子序列(ai1, ai2, ., aiK)，这里，这里1 = i1 i2 . iK = N。比如，对于序列

22、比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上，有它的一些上升子序列，如升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中等等。这些子序列中最长的长度是最长的长度是4，比如子序列，比如子序列(1, 3, 5, 8).你的任务，就是对于给定的序列，求出最长上升子序你的任务，就是对于给定的序列，求出最长上升子序列的长度。列的长度。动态规划基础讲解及案例分析解答问题描述输入数据输入数据输入的第一行是序列的长度输入的第一行是序列的长度N (1 = N = 1000)。第二行。第二行给出序列中的给出序列中的N 个整数，这些整数的取值范围都在个整数，这些整数的取值范围

23、都在0 到到10000。输出要求输出要求最长上升子序列的长度。最长上升子序列的长度。输入样例输入样例71 7 3 5 9 4 8输出样例输出样例4动态规划基础讲解及案例分析解答2、解题思路 n 如何把这个问题分解成子问题呢？经过分析，发现如何把这个问题分解成子问题呢？经过分析，发现 “求以求以ak（k=1, 2, 3N）为终点的最长上升子序列的长度）为终点的最长上升子序列的长度”是个是个好的子问题好的子问题这里把一个上升子序列中最右边的那个数，称这里把一个上升子序列中最右边的那个数，称为该子序列的为该子序列的“终点终点”。虽然这个子问题和原问题形式上并不。虽然这个子问题和原问题形式上并不完全一

24、样，但是只要这完全一样，但是只要这N 个子问题都解决了，那么这个子问题都解决了，那么这N 个子问个子问题的解中，最大的那个就是整个问题的解。题的解中，最大的那个就是整个问题的解。n 由上所述的子问题只和一个变量相关，就是数字的位置。因由上所述的子问题只和一个变量相关，就是数字的位置。因此序列中数的位置此序列中数的位置k 就是就是“状态状态”，而状态，而状态 k 对应的对应的“值值”，就是以就是以ak 做为做为“终点终点”的最长上升子序列的长度。这个问题的最长上升子序列的长度。这个问题的状态一共有的状态一共有N 个。状态定义出来后，转移方程就不难想了。个。状态定义出来后，转移方程就不难想了。 动

25、态规划基础讲解及案例分析解答2、解题思路 n假定假定MaxLen (k)表示以表示以ak 做为做为“终点终点”的最长上升子序列的最长上升子序列的长度，那么：的长度，那么：nMaxLen (1) = 1nMaxLen (k) = Max MaxLen (i)：1i k 且且 ai ak 且且 k1 + 1n这个状态转移方程的意思就是，这个状态转移方程的意思就是，MaxLen(k)的值，就是在的值，就是在ak 左边，左边，“终点终点”数值小于数值小于ak，且长度最大的那个上升子序列的，且长度最大的那个上升子序列的长度再加长度再加1。因为。因为ak 左边任何左边任何“终点终点”小于小于ak 的子序列

26、，加的子序列，加上上ak 后就能形成一个更长的上升子序列。后就能形成一个更长的上升子序列。n实 际 实 现 的 时 候 ， 可 以 不 必 编 写 递 归 函 数 ， 因 为 从实 际 实 现 的 时 候 ， 可 以 不 必 编 写 递 归 函 数 ， 因 为 从 MaxLen(1)就能推算出就能推算出MaxLen(2)，有了，有了MaxLen(1)和和MaxLen(2)就能推算出就能推算出MaxLen(3)动态规划基础讲解及案例分析解答3、参考程序int bMAX_N + 10;int aMaxLenMAX_N + 10;int main(void) int i, j, N; scanf(%

27、d, & N); for( i = 1;i = N;i + ) scanf(%d, & bi); aMaxLen1 = 1;动态规划基础讲解及案例分析解答3、参考程序 for( i = 2; i = N; i + ) /求以第求以第i 个数为终点的最长上升子序列的长度个数为终点的最长上升子序列的长度 int nTmp = 0; /记录第记录第i 个数左边子序列最大长度个数左边子序列最大长度 for( j = 1; j bj ) if( nTmp aMaxLenj ) nTmp = aMaxLenj; aMaxLeni = nTmp + 1; int nMax = -1; for

28、( i = 1;i = N;i + ) if( nMax aMaxLeni) nMax = aMaxLeni; printf(%dn, nMax); return 0;思考题：改进此程序，使之思考题：改进此程序，使之能够输出最长上升子序列能够输出最长上升子序列 动态规划基础讲解及案例分析解答Help Jimmy 1、问题描述、问题描述 Help Jimmy 是在下图所示的场景上完成的游戏：是在下图所示的场景上完成的游戏：动态规划基础讲解及案例分析解答问题描述 场景中包括多个长度和高度各不相同的平台。地面是最低场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。的平台，

29、高度为零，长度无限。 Jimmy 老鼠在时刻老鼠在时刻0 从高于所有平台的某处开始下落，它从高于所有平台的某处开始下落，它的下落速度始终为的下落速度始终为1 米米/秒。当秒。当Jimmy 落到某个平台上时，游落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是戏者选择让它向左还是向右跑，它跑动的速度也是1 米米/秒。秒。当当Jimmy 跑到平台的边缘时，开始继续下落。跑到平台的边缘时，开始继续下落。Jimmy 每次下每次下落的高度不能超过落的高度不能超过MAX 米，不然就会摔死，游戏也会结束。米，不然就会摔死，游戏也会结束。 设计一个程序，计算设计一个程序，计算Jimmy 到地面时

30、可能的最早时间。到地面时可能的最早时间。动态规划基础讲解及案例分析解答问题描述输入数据输入数据n 第一行是测试数据的组数第一行是测试数据的组数t（0 = t = 20）。每组测试数）。每组测试数据的第一行是四个整数据的第一行是四个整数N，X，Y，MAX，用空格分隔。，用空格分隔。N 是是平台的数目（不包括地面），平台的数目（不包括地面），X 和和Y 是是Jimmy 开始下落的位开始下落的位置的横竖坐标，置的横竖坐标，MAX 是一次下落的最大高度。接下来的是一次下落的最大高度。接下来的N 行行每行描述一个平台，包括三个整数，每行描述一个平台，包括三个整数，X1i，X2i和和Hi。Hi表示平台的高

31、度，表示平台的高度，X1i和和X2i表示平台左右端点的横坐表示平台左右端点的横坐标。标。1= N = 1000，-20000 = X, X1i, X2i = 20000，0 Hi Y = 20000（i = 1.N）。所有坐标）。所有坐标的单位都是米。的单位都是米。n Jimmy 的大小和平台的厚度均忽略不计。如果的大小和平台的厚度均忽略不计。如果Jimmy 恰好恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保叠或相连。测试数据保Jimmy 一定能安全到达地面。一定能安全到达地面。动态规划基础讲解及案例分析解答

32、问题描述输出要求输出要求对输入的每组测试数据，输出一个整数，对输入的每组测试数据，输出一个整数，Jimmy 到地面时可到地面时可能的最早时间。能的最早时间。输入样例输入样例13 8 17 200 10 80 10 134 14 3输出样例输出样例23动态规划基础讲解及案例分析解答2、解题思路 n 此题目的此题目的“子问题子问题”是什么呢？是什么呢？n Jimmy 跳到一块板上后，可以有两种选择，向左走或向右跳到一块板上后，可以有两种选择，向左走或向右走。走到左端和走到右端所需的时间，容易算出。走。走到左端和走到右端所需的时间，容易算出。n 如果我们能知道，以左端为起点到达地面的最短时间，和以如

33、果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面的最短时间，那么向左走还是向右走，就右端为起点到达地面的最短时间，那么向左走还是向右走，就很容选择了。很容选择了。n 因此，整个问题就被分解成两个子问题，即因此，整个问题就被分解成两个子问题，即Jimmy 所在位所在位置下方第一块板左端为起点到地面的最短时间，和右端为起点置下方第一块板左端为起点到地面的最短时间，和右端为起点到地面的最短时间。这两个子问题在形式上和原问题是完全一到地面的最短时间。这两个子问题在形式上和原问题是完全一致的。致的。n 将板子从上到下从将板子从上到下从1 开始进行无重复的编号开始进行无重复的编号(高度

34、相同的板高度相同的板子，哪块编号在前无所谓子，哪块编号在前无所谓)，那么，和上面两个子问题相关的，那么，和上面两个子问题相关的变量就只有板子的编号。变量就只有板子的编号。动态规划基础讲解及案例分析解答2、解题思路 n 所以，本题目的所以，本题目的“状态状态”就是板子编号，而一个就是板子编号，而一个“状态状态”对对应的应的“值值”有两部分，是两个子问题的解，即从该板子左端出有两部分，是两个子问题的解，即从该板子左端出发到达地面的最短时间，和从该板子右端出发到达地面的最短发到达地面的最短时间，和从该板子右端出发到达地面的最短时间。时间。n 不妨认为不妨认为Jimmy 开始的位置是一个编号为开始的位

35、置是一个编号为0，长度为，长度为0 的板的板子，假设子，假设LeftMinTime(k)表示从表示从k 号板子左端到地面的最短号板子左端到地面的最短时间，时间，RightMinTime(k)表示从表示从k 号板子右端到地面的最短号板子右端到地面的最短时间，那么，求板子时间，那么，求板子k 左端点到地面的最短时间的方法如下：左端点到地面的最短时间的方法如下：if ( 板子板子k 左端正下方没有别的板子左端正下方没有别的板子) if( 板子板子k 的高度的高度 h(k) 大于大于Max) LeftMinTime(k) = ; else LeftMinTime(k) = h(k);else if(

36、板子板子k 左端正下方的板子编号是左端正下方的板子编号是m ) LeftMinTime(k) = h(k)-h(m) + Min(LeftMinTime(m)+Lx(k)-Lx(m), RightMinTime(m)+Rx(m)-Lx(k); 动态规划基础讲解及案例分析解答2、解题思路 n 上面，上面，h(i)就代表就代表i 号板子的高度，号板子的高度，Lx(i)就代表就代表i 号板子左号板子左端点的横坐标，端点的横坐标，Rx(i)就代表就代表i号板子右端点的横坐标。那么号板子右端点的横坐标。那么 h(k)-h(m) 当然就是从当然就是从k 号板子跳到号板子跳到m 号板子所需要的时间，号板子所

37、需要的时间，Lx(k)-Lx(m) 就是从就是从m 号板子的落脚点走到号板子的落脚点走到m 号板子左端点号板子左端点的时间，的时间，Rx(m)-Lx(k)就是从就是从m号板子的落脚点走到右端点号板子的落脚点走到右端点所需的时间。所需的时间。n 求求RightMinTime(k)的过程类似。的过程类似。n 不妨认为不妨认为Jimmy 开始的位置是一个编号为开始的位置是一个编号为0，长度为，长度为0 的板的板子，那么整个问题就是要求子，那么整个问题就是要求LeftMinTime(0)。n 输入数据中，板子并没有按高度排序，所以程序中一定要首输入数据中，板子并没有按高度排序，所以程序中一定要首先将板

38、子排序。先将板子排序。动态规划基础讲解及案例分析解答3、参考程序#include #include #include #define MAX_N 1000#define INFINITE 1000000int t, n, x, y, max;struct Platform int Lx, Rx, h; ;Platform aPlatformMAX_N + 10;int aLeftMinTimeMAX_N + 10;int aRightMinTimeMAX_N + 10;int MyCompare( const void * e1, const void * e2 ) Platform * p1

39、, * p2; p1 = (Platform * ) e1; p2 = (Platform * ) e2; return p2-h - p1-h; /从大到小排列从大到小排列动态规划基础讲解及案例分析解答3、参考程序int MinTime( int L, bool bLeft ) int y = aPlatformL.h; int i, x; if( bLeft ) x = aPlatformL.Lx; else x = aPlatformL.Rx; for( i = L + 1;i = n;i + ) /找到下一张板子找到下一张板子 if( aPlatformi.Lx = x) break;

40、 if( i max )/太高太高 return INFINITE; 动态规划基础讲解及案例分析解答3、参考程序 else /没找到没找到 if( y max )/离地面太高离地面太高 return INFINITE; else return y; /特殊情况处理完毕特殊情况处理完毕 int nLeftTime = y - aPlatformi.h + x - aPlatformi.Lx; int nRightTime = y - aPlatformi.h + aPlatformi.Rx - x; if( aLeftMinTimei = -1 )/还没有存储值还没有存储值 aLeftMinTi

41、mei = MinTime(i, true); if( aRightMinTimei = -1 ) aRightMinTimei = MinTime(i, false); nLeftTime += aLeftMinTimei; nRightTime += aRightMinTimei; if( nLeftTime nRightTime ) return nLeftTime; return nRightTime;动态规划基础讲解及案例分析解答3、参考程序int main(void) scanf(%d, &t); for( int i = 0;i t; i + ) memset(aLeft

42、MinTime, -1, sizeof(aLeftMinTime); memset(aRightMinTime, -1, sizeof(aRightMinTime); scanf(%d%d%d%d, &n, &x, &y, &max); aPlatform0.Lx = x; aPlatform0.Rx = x;/长度为长度为0的板子的板子 aPlatform0.h = y; for( int j = 1; j = n; j + ) scanf(%d%d%d, & aPlatformj.Lx, & aPlatformj.Rx, & aPla

43、tformj.h); qsort(aPlatform, n+1, sizeof(Platform), MyCompare); printf(%dn, MinTime(0, true); return 0;思考题：重新编写此程序，要求不使用递思考题：重新编写此程序，要求不使用递归函数归函数动态规划基础讲解及案例分析解答34第十课动态规划动态规划( (II) )综合实践考核动态规划基础讲解及案例分析解答最长公共子序列 1、问题描述、问题描述 我们称序列我们称序列Z = 是序列是序列X = 的子序列当且仅当存在严格上升的序列的子序列当且仅当存在严格上升的序列，使得对使得对j = 1, 2, . ,k

44、, 有有xij = zj。比如。比如Z = 是是X = 的子序列。的子序列。现在给出两个序列现在给出两个序列X 和和Y，你的任务是找到，你的任务是找到X 和和Y 的最大公共的最大公共子序列，也就是说要找到一个最长的序列子序列，也就是说要找到一个最长的序列Z，使得，使得Z 既是既是X 的的子序列也是子序列也是Y 的子序列。的子序列。输入数据输入数据输入包括多组测试数据。每组数据包括一行，给出两个长度不输入包括多组测试数据。每组数据包括一行，给出两个长度不超过超过200 的字符串，表示两个序列。两个字符串之间由若干的字符串，表示两个序列。两个字符串之间由若干个空格隔开。个空格隔开。动态规划基础讲解

45、及案例分析解答问题描述 输出要求输出要求 对每组输入数据，输出一行，给出两个序列的最大公共子序对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。列的长度。 输入样例输入样例 abcfbc abfcab programming contest abcd mnp 输出样例输出样例 4 2 0动态规划基础讲解及案例分析解答2、解题思路 n用字符数组用字符数组s1、s2存放两个字符串，用存放两个字符串，用s1i表示表示s1中的第中的第i 个字符，个字符，s2j表示表示s2中的第中的第j个字符（字符编号从个字符（字符编号从1 开始），开始），用用s1i表示表示s1的前的前i个字符所构成的子串

46、，个字符所构成的子串，s2j表示表示s2的前的前j个字个字符构成的子串，符构成的子串，MaxLen(i,j)表示表示s1i 和和s2j 的最长公共子序列的最长公共子序列的长度，那么递推关系如下：的长度，那么递推关系如下：nif( i =0 | j = 0 ) n MaxLen(i, j) = 0 /两个空串的最长公共子序列长度是两个空串的最长公共子序列长度是0nelse if( s1i = s2j )n MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1;nelse n MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j);动态

47、规划基础讲解及案例分析解答2、解题思路 n 显然本题目的显然本题目的“状态状态”就是就是s1 中的位置中的位置i 和和s2 中的位置中的位置j。n “值值”就是就是MaxLen(i, j)。n 状态的数目是状态的数目是s1 长度和长度和s2 长度的乘积。可长度的乘积。可以用一个二维数组来存储各个状态下的以用一个二维数组来存储各个状态下的“值值”。n 本问题的两个子问题，和原问题形式完全一本问题的两个子问题，和原问题形式完全一致的，只不过规模小了一点。致的，只不过规模小了一点。动态规划基础讲解及案例分析解答3、参考程序#include #include #define MAX_LEN 1000c

48、har sz1MAX_LEN;char sz2MAX_LEN;int aMaxLenMAX_LENMAX_LEN;int main(void) while( scanf(%s%s, sz1+1 ,sz2+1 ) 0 ) int nLength1 = strlen( sz1+1); int nLength2 = strlen( sz2+1); int i, j; for( i = 0;i = nLength1; i + ) aMaxLeni0 = 0; for( j = 0;j = nLength2; j + ) aMaxLen0j = 0;动态规划基础讲解及案例分析解答3、参考程序 for(

49、i = 1;i = nLength1;i + ) for( j = 1; j nLen2 ) aMaxLenij = nLen1; else aMaxLenij = nLen2; printf(%dn, aMaxLennLength1nLength2); return 0;动态规划基础讲解及案例分析解答陪审团的人选 1、问题描述、问题描述 在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选定。陪审团是由法官从公众中挑选的。先随机挑选n 个人作为个人作为陪审团的候选人，然后再从这陪审团的候选人，然后再从

50、这n 个人中选个人中选m 人组成陪审团。人组成陪审团。选选m 人的办法是：人的办法是： 控方和辩方会根据对候选人的喜欢程度，给所有候选人打控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从分，分值从0 到到20。为了公平起见，法官选出陪审团的原则。为了公平起见，法官选出陪审团的原则是：选出的是：选出的m 个人，必须满足辩方总分和控方总分的差的绝个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最的绝对值相同，那么选辩控双方总分之和最大的

51、方案即可。最终选出的方案称为陪审团方案。终选出的方案称为陪审团方案。动态规划基础讲解及案例分析解答问题描述输入数据输入数据输入包含多组数据。每组数据的第一行是两个整数输入包含多组数据。每组数据的第一行是两个整数n 和和m，n 是候选人数目，是候选人数目，m 是陪审团人数。注意，是陪审团人数。注意，1=n=200, 1=m=20 而且而且 m=n。接下来的。接下来的n 行，每行表示一个候行，每行表示一个候选人的信息，它包含选人的信息，它包含2 个整数，先后是控方和辩方对该候选人个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从的打分。候选人按出现的先后从1开始编号。两组有效数据之开始

52、编号。两组有效数据之间以空行分隔。最后一组数据间以空行分隔。最后一组数据n=m=0输出要求输出要求对每组数据，先输出一行，表示答案所属的组号对每组数据，先输出一行，表示答案所属的组号, 如如 Jury #1, Jury #2, 等。接下来的一行要象例子那样输出陪审团等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。须以一个空行结束。动态规划基础讲解及案例分析解答问题描述输入样

53、例输入样例4 21 22 34 16 20 0输出样例输出样例Jury #1Best jury has value 6 for prosecution and value 4 for defence:2 3动态规划基础讲解及案例分析解答2、解题思路 n为叙述方便，将任一选择方案中，辩方总分和控方总分之差为叙述方便，将任一选择方案中，辩方总分和控方总分之差简称为简称为“辩控差辩控差”，辩方总分和控方总分之和称为，辩方总分和控方总分之和称为“辩控和辩控和”。n第第i 个候选人的辩方总分和控方总分之差记为个候选人的辩方总分和控方总分之差记为V(i)，辩方总分，辩方总分和控方总分之和记为和控方总分之和

54、记为S(i)。n现用现用f(j, k)表示，取表示，取j 个候选人，使其辩控差为个候选人，使其辩控差为k 的所有方案的所有方案中，辩控和最大的那个方案（该方案称为中，辩控和最大的那个方案（该方案称为“方案方案f(j, k)”）的）的辩控和。辩控和。并且，我们还规定，如果没法选并且，我们还规定，如果没法选j 个人，使其辩控差个人，使其辩控差为为k，那么，那么f(j, k)的值就为的值就为-1，也称方案，也称方案f(j, k)不可行。不可行。n本题是要求选出本题是要求选出m 个人，那么，如果对个人，那么，如果对k 的所有可能的取值，的所有可能的取值，求出了所有的求出了所有的f(m, k) (-20

55、m k 20m)，那么陪审团，那么陪审团方案自然就很容易找到了。方案自然就很容易找到了。动态规划基础讲解及案例分析解答2、解题思路 n问题的关键是建立递推关系。显然，方案问题的关键是建立递推关系。显然，方案f(j, k)是由某个可是由某个可行的方案行的方案f(j-1, x)( -20m x 20m)演化而来的。演化而来的。n可行方案可行方案f(j-1, x)能演化成方案能演化成方案f(j, k)的必要条件是：存在的必要条件是：存在某个候选人某个候选人i，i 在方案在方案f(j-1, x)中没有被选上，且中没有被选上，且x+V(i) = k。在所有满足该必要条件的在所有满足该必要条件的f(j-1

56、, x)中，选出中，选出 f(j-1, x) + S(i) 的值最大的那个，那么方案的值最大的那个，那么方案f(j-1, x)再加上候选人再加上候选人i，就演变，就演变成了方案成了方案 f(j, k)。n由上面知一个方案都选了哪些人需要全部记录下来。不妨由上面知一个方案都选了哪些人需要全部记录下来。不妨将将方案方案f(j, k)中最后选的那个候选人的编号，记在二维数组的元中最后选的那个候选人的编号，记在二维数组的元素素pathjk中中。那么方案。那么方案f(j, k)的倒数第二个人选的编号，的倒数第二个人选的编号，就是就是pathj-1k-Vpathjk。n假定最后算出了方案的辩控差是假定最后

57、算出了方案的辩控差是k，那么从，那么从pathmk出发，出发，就能顺藤摸瓜一步步求出所有被选中的候选人。就能顺藤摸瓜一步步求出所有被选中的候选人。动态规划基础讲解及案例分析解答2、解题思路 n初始条件，只能确定初始条件，只能确定f(0, 0) = 0。由此出发，一步步自底向。由此出发，一步步自底向上递推，就能求出所有的可行方案上递推，就能求出所有的可行方案f(m, k)( -20m k 20m)。n实际解题的时候，会用一个二维数组实际解题的时候，会用一个二维数组f 来存放来存放f(j, k)的值。而的值。而且，由于题目中辩控差的值且，由于题目中辩控差的值k 可以为负数，而程序中数租下标可以为负

58、数，而程序中数租下标不能为负数，所以，在程序中不妨将辩控差的值都加上不能为负数，所以，在程序中不妨将辩控差的值都加上20m，以免下标为负数导致出错，即题目描述中，如果辩，以免下标为负数导致出错，即题目描述中，如果辩控差为控差为0，则在程序中辩控差为，则在程序中辩控差为20m。动态规划基础讲解及案例分析解答3、参考程序#include #include #include int f301000;int Path301000;int P300; /控方打分控方打分int D300; /辩方打分辩方打分int Answer30; /存放最终方案的人选存放最终方案的人选int CompareInt(c

59、onst void * e1, const void * e2) return * (int *) e1) - * (int *) e2);动态规划基础讲解及案例分析解答3、参考程序int main(void) int i, j, k; int t1, t2; int n, m; int nMinP_D; /辩控双方总分一样时的辩控差辩控双方总分一样时的辩控差 int nCaseNo;/测试数据编号测试数据编号 nCaseNo=0; scanf(%d%d, &n, &m); while(n+m) nCaseNo+; for(i=1;i=n;i+) scanf(%d%d, &am

60、p;Pi, &Di); memset(f, -1, sizeof(f); memset(Path, 0, sizeof(Path); nMinP_D=m*20; /题目中的辩控差为题目中的辩控差为0 /对应到程序中辩控差就是对应到程序中辩控差就是m*20 f0nMinP_D=0; /选选0 个人辩控差为个人辩控差为0 的方案，其辩控和就是的方案，其辩控和就是0动态规划基础讲解及案例分析解答3、参考程序 for(j=0;jm;j+) /每次循环选出第每次循环选出第j 个人，共要选出个人，共要选出m 人人 for(k=0;k=0) /方案方案 f(j, k)可行可行 for(i=1;ifj+1k+Pi-Di) /即时判别记住更合适的即时判别记住更合适的f(j,k) t1=j; t2=k; while(t10&Patht1t2!=i) /t2减去编号为减