动态规划案例分析.ppt

动态规划动态规划案例分析案例分析8/15/20241数字三角形数字三角形 1、问题描述、问题描述 上图给出了一个数字三角形从三角形的顶部到底部有很上图给出了一个数字三角形从三角形的顶部到底部有很多条不同的路径对于每条路径，把路径上面的数加起来可以多条不同的路径对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径你的任务就是求出得到一个和，和最大的路径称为最佳路径你的任务就是求出最佳路径上的数字之和最佳路径上的数字之和注意：路径上的每一步只能从一个数走到下一层上和它最近的注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数左边的数或者右边的数问题描述输入数据输入数据 输入的第一行是一个整数输入的第一行是一个整数N (1 < N <= 100)，，给出三角形的行数下面的给出三角形的行数下面的N 行给出数字三角形数行给出数字三角形数字三角形上的数的范围都在字三角形上的数的范围都在0 和和100 之间输出要求输出要求输出最大的和输出最大的和问题描述输入样例输入样例573 88 1 02 7 4 44 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 100int D[MAX_NUM + 10][MAX_NUM + 10];int N;int MaxSum( int r, int j){if( r == N )return D[r][j];int nSum1 = MaxSum(r+1, j);int nSum2 = MaxSum(r+1, j+1);if( nSum1 > nSum2 )return nSum1+D[r][j];return nSum2+D[r][j]; }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", &D[i][j]);printf("%d", MaxSum(1, 1));return 0;}程序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），那么就能得到右面的三角形：），那么就能得到右面的三角形：11 11 2 11 3 3 11 4 6 4 173 88 1 02 7 4 44 5 2 6 5程序分析 n 从上图可以看出，最后一行的计算次数总和是从上图可以看出，最后一行的计算次数总和是16，倒数第二行，倒数第二行的计算次数总和是的计算次数总和是8不难总结出规律，对于不难总结出规律，对于N 行的三角形，总的行的三角形，总的计算次数是计算次数是2^0 +2^1+2^2+…+2^(N-1)=2^N-1。

当当N= 100 时，总的计算次数是一个让人无法接受的大数字时，总的计算次数是一个让人无法接受的大数字n 既然问题出在重复计算，那么解决的办法，当然就是，一个值既然问题出在重复计算，那么解决的办法，当然就是，一个值一旦算出来，就要记住，以后不必重新计算即第一次算出一旦算出来，就要记住，以后不必重新计算即第一次算出MaxSum(r, j)的值时，就将该值存放起来，下次再需要计算的值时，就将该值存放起来，下次再需要计算MaxSum(r, j)时，直接取用存好的值即可，不必再次调用时，直接取用存好的值即可，不必再次调用MaxSum 进行函数递归计算了这样，每个进行函数递归计算了这样，每个MaxSum(r, j)都只都只需要计算需要计算1 次即可，那么总的计算次数（即调用次即可，那么总的计算次数（即调用MaxSum 函数的函数的次数）就是三角形中的数字总数，即次数）就是三角形中的数字总数，即1+2+3+…+N = N(N+1)/2n 如何存放计算出来的如何存放计算出来的MaxSum（（r, j）值呢？显然，用一个二）值呢？显然，用一个二维数组维数组aMaxSum[N][N]就能解决就能解决aMaxSum[r][j]就存放就存放MaxSum(r, j)的计算结果。

下次再需要的计算结果下次再需要MaxSum(r, j)的值时，的值时，不必再调用不必再调用MaxSum 函数，只需直接取函数，只需直接取aMaxSum[r][j]的值即的值即可4、参考程序 II#include #include #define MAX_NUM 100int D[MAX_NUM + 10][MAX_NUM + 10];int N;int aMaxSum[MAX_NUM + 10][MAX_NUM + 10];int MaxSum( int r, int j){ if( r == N ) return D[r][j]; if( aMaxSum[r+1][j] == -1 ) //如果如果MaxSum(r+1, j)没有计算过没有计算过 aMaxSum[r+1][j] = MaxSum(r+1, j); if( aMaxSum[r+1][j+1] == -1) aMaxSum[r+1][j+1] = MaxSum(r+1, j+1); if( aMaxSum[r+1][j] > aMaxSum[r+1][j+1] ) return aMaxSum[r+1][j] +D[r][j]; return aMaxSum[r+1][j+1] + D[r][j];}4、参考程序 IIint main(void){ int m; scanf("%d", & N); //将将 aMaxSum 全部置成全部置成-1, 开始时所有的开始时所有的 MaxSum(r, j)都没有算过都没有算过 memset(aMaxSum, -1, sizeof(aMaxSum)); for( int i = 1; i <= N; i ++ ) for( int j = 1; j <= i; j ++ ) scanf("%d", & D[i][j]); printf("%d", MaxSum(1, 1)); return 0;}程序II分析 这种将一个问题分解为子问题递归求解，并且将中间结果这种将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做保存以避免重复计算的办法，就叫做“动态规划动态规划”。

动态规动态规划通常用来求最优解，能用动态规划解决的求最优解问题，划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的必须满足，最优解的每个局部解也都是最优的以上题为例，以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径字出发到达到底部的最佳路径 实际上，递归的思想在编程时未必要实现为递归函数实际上，递归的思想在编程时未必要实现为递归函数在上面的例子里，有递推公式：在上面的例子里，有递推公式： 因此，不需要写递归函数，从因此，不需要写递归函数，从aMaxSum[N-1]这一行元这一行元素开始向上逐行递推，就能求得素开始向上逐行递推，就能求得aMaxSum[1][1]的值了5、参考程序 IIIint D[MAX_NUM + 10][MAX_NUM + 10];int N;int aMaxSum[MAX_NUM + 10][MAX_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", &D[i][j]); for( j = 1; j <= N; j ++ ) aMaxSum[N][j] = D[N][j]; for( i = N ; i > 1 ; i -- ) for( j = 1; j < i ; j ++ ) { if( aMaxSum[i][j] > aMaxSum[i][j+1] ) aMaxSum[i-1][j] = aMaxSum[i][j] + D[i-1][j]; else aMaxSum[i-1][j] = aMaxSum[i][j+1] + D[i-1][j]; } printf("%d", aMaxSum[1][1]); 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 < b2 < ... < bS 的的时时候候，，我我们们称称这这个个序序列列是是上上升升的的对对于于给给定定的的一一个个序序列列(a1, a2, ..., aN)，，我我们们可可以以得得到到一一些些上上升升的的子子序序列列(ai1, ai2, ..., aiK)，，这这里里1 <= i1 < i2 < ...

输出要求输出要求最长上升子序列的长度最长上升子序列的长度输入样例输入样例71 7 3 5 9 4 8输出样例输出样例42、解题思路 n 如何把这个问题分解成子问题呢？经过分析，发现如何把这个问题分解成子问题呢？经过分析，发现 “求以求以ak（（k=1, 2, 3…N）为终点的最长上升子序列的长度）为终点的最长上升子序列的长度”是个好是个好的子问题的子问题――这里把一个上升子序列中最右边的那个数，称为这里把一个上升子序列中最右边的那个数，称为该子序列的该子序列的“终点终点”虽然这个子问题和原问题形式上并不完虽然这个子问题和原问题形式上并不完全一样，但是只要这全一样，但是只要这N 个子问题都解决了，那么这个子问题都解决了，那么这N 个子问题个子问题的解中，最大的那个就是整个问题的解的解中，最大的那个就是整个问题的解n 由上所述的子问题只和一个变量相关，就是数字的位置因由上所述的子问题只和一个变量相关，就是数字的位置因此序列中数的位置此序列中数的位置k 就是就是“状态状态”，而状态，而状态 k 对应的对应的“值值”，，就是以就是以ak 做为做为“终点终点”的最长上升子序列的长度这个问题的的最长上升子序列的长度。

这个问题的状态一共有状态一共有N 个状态定义出来后，转移方程就不难想了状态定义出来后，转移方程就不难想了 2、解题思路 n假假定定MaxLen (k)表表示示以以ak 做做为为“终终点点”的的最最长长上上升升子子序序列列的长度，那么：的长度，那么：nMaxLen (1) = 1nMaxLen (k) = Max { MaxLen (i)：：1 b[j] ) { if( nTmp < aMaxLen[j] ) nTmp = aMaxLen[j]; } } aMaxLen[i] = nTmp + 1; } int nMax = -1; for( i = 1;i <= N;i ++ ) if( nMax < aMaxLen[i]) nMax = aMaxLen[i]; printf("%d\n", nMax); return 0;}思考题：改进此程序，使之思考题：改进此程序，使之能够输出最长上升子序列能够输出最长上升子序列 最长公共子序列最长公共子序列 1、问题描述、问题描述 我我们们称称序序列列Z = < z1, z2, ..., zk >是是序序列列X = < x1, x2, ..., xm >的的子子序序列列当当且且仅仅当当存存在在严严格格上上升升的的序序列列< i1, i2, ..., ik >，，使使得得对对j = 1, 2, ... ,k, 有有xij = zj。