动态规划案例分析.ppt

2019/7/26,1,动态规划 案例分析,数字三角形,1、问题描述,上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。 注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。,问题描述,输入数据 输入的第一行是一个整数N (1 N = 100)，给出三角形的行数。下面的N 行给出数字三角形。数字三角形上的数的范围都在0 和100 之间。 输出要求 输出最大的和。,问题描述,输入样例 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出样例 30,2、解题思路,这道题目可以用递归的方法解决。基本思路是： 以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)；如果走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 100 int DMAX_NUM + 10MAX_NUM + 10; int N; int MaxSum( int r, int j) if( r = N ) return Drj; int nSum1 = MaxSum(r+1, j); int nSum2 = MaxSum(r+1, j+1); if( nSum1 nSum2 ) return nSum1+Drj; return nSum2+Drj; ,3、参考程序 I,int main(void) int m; scanf(“%d“, ,程序I分析,上面的程序，效率非常低，在N 值并不大，比如N=100 的时候，就慢得几乎永远算不出结果了。 为什么？是因为过多的重复计算。 我们不妨将对MaxSum 函数的一次调用称为一次计算。那么，每次计算MaxSum(r, j)的时候，都要计算一次MaxSum(r+1, j+1)，而每次计算MaxSum(r, j+1)的时候，也要计算一次MaxSum(r+1, j+1)。重复计算因此产生。 在题目中给出的例子里，如果我们将MaxSum(r, j)被计算的次数都写在位置（r, j），那么就能得到右面的三角形：,1 1 1 1 2 1 1 3 3 1 1 4 6 4 1,7 3 8 8 1 0 2 7 4 4 4 5 2 6 5,程序分析,从上图可以看出，最后一行的计算次数总和是16，倒数第二行的计算次数总和是8。不难总结出规律，对于N 行的三角形，总的计算次数是20 +21+22+2(N-1)=2N-1。当N= 100 时，总的计算次数是一个让人无法接受的大数字。 既然问题出在重复计算，那么解决的办法，当然就是，一个值一旦算出来，就要记住，以后不必重新计算。即第一次算出MaxSum(r, j)的值时，就将该值存放起来，下次再需要计算MaxSum(r, j)时，直接取用存好的值即可，不必再次调用MaxSum 进行函数递归计算了。这样，每个MaxSum(r, j)都只需要计算1 次即可，那么总的计算次数（即调用MaxSum 函数的次数）就是三角形中的数字总数，即1+2+3+N = N(N+1)/2。 如何存放计算出来的MaxSum（r, j）值呢？显然，用一个二维数组aMaxSumNN就能解决。aMaxSumrj就存放MaxSum(r, j)的计算结果。下次再需要MaxSum(r, j)的值时，不必再调用MaxSum 函数，只需直接取aMaxSumrj的值即可。,4、参考程序 II,#include #include #define MAX_NUM 100 int 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 ) /如果MaxSum(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、参考程序 II,int main(void) int m; scanf(“%d“, ,程序II分析,这种将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。 实际上，递归的思想在编程时未必要实现为递归函数。在上面的例子里，有递推公式：,因此，不需要写递归函数，从aMaxSumN-1这一行元素开始向上逐行递推，就能求得aMaxSum11的值了。,5、参考程序 III,int DMAX_NUM + 10MAX_NUM + 10; int N; int aMaxSumMAX_NUM + 10MAX_NUM + 10; int main(void) int i, j; scanf(“%d“, ,思考题：上面的几个程序只算出了最佳路径的数字之和。如果要求输出最佳路径上的每个数字，该怎么办？,动态规划解题的一般思路,许多求最优解的问题可以用动态规划来解决。 首先要把原问题分解为若干个子问题。注意单纯的递归往往会导致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就要被保存，所以每个子问题只需求解一次。 子问题经常和原问题形式相似，有时甚至完全一样，只不过规模从原来的n 变成了n-1，或从原来的nm 变成了n(m-1) 等等。 找到子问题，就意味着找到了将整个问题逐渐分解的办法。 分解下去，直到最底层规模最小的的子问题可以一目了然地看出解。 每一层子问题的解决，会导致上一层子问题的解决，逐层向上，就会导致最终整个问题的解决。 如果从最底层的子问题开始，自底向上地推导出一个个子问题的解，那么编程的时候就不需要写递归函数。,动态规划解题的一般思路,用动态规划解题时，将和子问题相关的各个变量的一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题，所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。 比如数字三角形，子问题就是“从位于(r，j)数字开始，到底边路径的最大和”。这个子问题和两个变量r 和j 相关，那么一个“状态”，就是r, j 的一组取值，即每个数字的位置就是一个“状态”。该“状态”所对应的“值”，就是从该位置的数字开始，到底边的最佳路径上的数字之和。 定义出什么是“状态”，以及在该 “状态”下的“值”后，就要找出不同的状态之间如何迁移即如何从一个或多个“值”已知的 “状态”，求出另一个“状态”的“值”。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。,动态规划解题的一般思路,用动态规划解题，如何寻找“子问题”，定义“状态”，“状态转移方程”是什么样的，并没有一定之规，需要具体问题具体分析，题目做多了就会有感觉。 甚至，对于同一个问题，分解成子问题的办法可能不止一种，因而“状态”也可以有不同的定义方法。不同的“状态”定义方法可能会导致时间、空间效率上的区别。,最长上升子序列,1、问题描述,一个数的序列bi，当b1 b2 . bS 的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ., aN)，我们可以得到一些上升的子序列(ai1, ai2, ., aiK)，这里1 = i1 i2 . iK = N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。,问题描述,输入数据 输入的第一行是序列的长度N (1 = N = 1000)。第二行给出序列中的N 个整数，这些整数的取值范围都在0 到10000。 输出要求 最长上升子序列的长度。 输入样例 7 1 7 3 5 9 4 8 输出样例 4,2、解题思路,如何把这个问题分解成子问题呢？经过分析，发现 “求以ak（k=1, 2, 3N）为终点的最长上升子序列的长度”是个好的子问题这里把一个上升子序列中最右边的那个数，称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要这N 个子问题都解决了，那么这N 个子问题的解中，最大的那个就是整个问题的解。 由上所述的子问题只和一个变量相关，就是数字的位置。因此序列中数的位置k 就是“状态”，而状态 k 对应的“值”，就是以ak 做为“终点”的最长上升子序列的长度。这个问题的状态一共有N 个。状态定义出来后，转移方程就不难想了。,2、解题思路,假定MaxLen (k)表示以ak 做为“终点”的最长上升子序列的长度，那么： MaxLen (1) = 1 MaxLen (k) = Max MaxLen (i)：1i k 且 ai ak 且 k1 + 1 这个状态转移方程的意思就是，MaxLen(k)的值，就是在ak 左边，“终点”数值小于ak，且长度最大的那个上升子序列的长度再加1。因为ak 左边任何“终点”小于ak 的子序列，加上ak 后就能形成一个更长的上升子序列。 实际实现的时候，可以不必编写递归函数，因为从 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(“%d“, ,3、参考程序,for( i = 2; i bj ) if( nTmp aMaxLenj ) nTmp = aMaxLenj; aMaxLeni = nTmp + 1; int nMax = -1; for( i = 1;i = N;i + ) if( nMax aMaxLeni) nMax = aMaxLeni; printf(“%dn“, nMax); return 0; ,思考题：改进此程序，使之能够输出最长上升子序列,最长公共子序列,1、问题描述,我们称序列Z = 是序列X = 的子序列当且仅当存在严格上升的序列，使得对j = 1, 2, . ,k, 有xij = zj。比如Z = 是X = 的子序列。 现在给出两个序列X 和Y，你的任务是找到X 和Y 的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z 既是X 的子序列也是Y 的子序列。 输入数据 输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200 的字符串，表示两个序列。两个字符串之间由若干个空格隔开。,问题描述,输出要求 对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。 输入样例 abcfbc abfcab programming contest abcd mnp 输出样例 4 2 0,2、解题思路,用字符数组s1、s2存放两个字符串，用s1i表示s1中的第i 个字符，s2j表示s2中的第j个字符（字符编号从1 开始），用s1i表示s1的前i个字符所构成的子串，s2j表示s2的前j个字符构成的子串，MaxLen(i,j)表示s1i 和s2j 的最长公共子序列的长度，那么递推关系如下： if( i =0 | j = 0 ) MaxLen(i, j) = 0 /两个空串的最长公共子序列长度是0 else if( s1i = s2j ) MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1; else MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j);,2、解题思路,显然本题目的“状态”就是s1 中的位置i 和s2 中的位置j。 “值”就是MaxLen(i, j)。 状态的数目是s1 长度和s2 长度的乘积。可以用一个二维数组来存储各个状态下的“值”。 本问题的两个子问题，和原问题形式完全一致的，只不过规模小了一点。,3、参考程序,#include #include #define MAX_LEN 1000 char 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 + )