动态规划案例分析.ppt

动态规划 案例分析 2019/2/91 数字三角形 1、问题描述 上图给出了一个数字三角形。从三角形的顶部到底部有很 多条不同的路径。对于每条路径，把路径上面的数加起来可以 得到一个和，和最大的路径称为最佳路径。你的任务就是求出 最佳路径上的数字之和。 注意：路径上的每一步只能从一个数走到下一层上和它最近的 左边的数或者右边的数。 问题描述 输入数据 输入的第一行是一个整数N (1 #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“, for( int i = 1; i #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“, /将 aMaxSum 全部置成-1, 开始时所有的 MaxSum(r, j)都没有算过 memset(aMaxSum, -1, sizeof(aMaxSum); for( int i = 1; i 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 许多求最优解的问题可以用动态规划来解决。 n 首先要把原问题分解为若干个子问题。注意单纯的递归往往会导 致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就 要被保存，所以每个子问题只需求解一次。 n 子问题经常和原问题形式相似，有时甚至完全一样，只不过规模 从原来的n 变成了n-1，或从原来的n×m 变成了n×(m-1) 等 等。 n 找到子问题，就意味着找到了将整个问题逐渐分解的办法。 n 分解下去，直到最底层规模最小的的子问题可以一目了然地看出 解。 n 每一层子问题的解决，会导致上一层子问题的解决，逐层向上， 就会导致最终整个问题的解决。 n 如果从最底层的子问题开始，自底向上地推导出一个个子问题的 解，那么编程的时候就不需要写递归函数。 动态规划解题的一般思路 n 用动态规划解题时，将和子问题相关的各个变量的一组取值 ，称之为一个“状态”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的 解。 n 比如数字三角形，子问题就是“从位于(r，j)数字开始，到底 边路径的最大和”。这个子问题和两个变量r 和j 相关，那么一 个“状态”，就是r, j 的一组取值，即每个数字的位置就是一个“ 状态”。该“状态”所对应的“值”，就是从该位置的数字开始， 到底边的最佳路径上的数字之和。 n 定义出什么是“状态”，以及在该 “状态”下的“值”后，就要找 出不同的状态之间如何迁移即如何从一个或多个“值”已知 的 “状态”，求出另一个“状态”的“值”。状态的迁移可以用递推 公式表示，此递推公式也可被称作“状态转移方程”。 动态规划解题的一般思路 n用动态规划解题，如何寻找“子问题”，定义“状态”，“状态转 移方程”是什么样的，并没有一定之规，需要具体问题具体分 析，题目做多了就会有感觉。 n甚至，对于同一个问题，分解成子问题的办法可能不止一种 ，因而“状态”也可以有不同的定义方法。不同的“状态”定义方 法可能会导致时间、空间效率上的区别。 最长上升子序列 1、问题描述 一个数的序列bi，当b1 bj ) if( nTmp 是序列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、解题思路 n用字符数组s1、s2存放两个字符串，用s1i表示s1中的第i 个字符，s2j表示s2中的第j个字符（字符编号从1 开始）， 用s1i表示s1的前i个字符所构成的子串，s2j表示s2的前j个字 符构成的子串，MaxLen(i,j)表示s1i 和s2j 的最长公共子序列 的长度，那么递推关系如下： nif( i =0 | j = 0 ) n MaxLen(i, j) = 0 /两个空串的最长公共子序列长度是0 nelse 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); 2、解题思路 n 显然本题目的“状态”就是s1 中的位置i 和s2 中的位置j。 n “值”就是MaxLen(i, j)。 n 状态的数目是s1 长度和s2 长度的乘积。可 以用一个二维数组来存储各个状态下的“值”。 n 本问题的两个子问题，和原问题形式完全一 致的，只不过规模小了一点。 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 nLen2 ) aMaxLenij = nLen1; else aMaxLenij = nLen2; printf(“%dn“, aMaxLennLength1nLength2); return 0; 最大子序列和问题 1、问题描述 有一串数字（可正可负的int，放在数组nums里 ），要求找到起始位置start和终止位置end，使得从 start位置到end位置的所有数字之和最大，返回这个 最大值max。用动态规划算法实现. 2、解题思路 n设 fx 为以 numsx 终止且包含 numsx 的最大子序列 的和，有： n f1 = nums1; fx+1 = fx 0 ? fx + numsx+1 : numsx+1 那么最大子序列的和就是 f1 fn 中最大的一个。 3、参考程序 void MaxSubseq_DP(int nums, int count, int / fx+1 = fx 0 ? fx + numsx+1 : numsx+1 / 那么最大子序列的和就是 f1 fn 中最大的一个 int start, max; int i; start = resStart = resEnd = 0; /初始化当前子序列和最大子序列为nums0 max = resMax = nums0; 3、参考程序 for (i = 1; i 0) max += numsi; else max = numsi; /抛弃当前子序列 start = i; /开始新的子序列搜索 if (resMax max) /更新最大子序列 resMax = max; resStart = start; resEnd = i; /for return;