动态规划基础讲解及经典案例分析解答课件_1.ppt

数字三角形 问题描述 问题描述 2、解题思路 3、参考程序 I 3、参考程序 I 程序I分析 程序分析 4、参考程序 II 4、参考程序 II 程序II分析 5、参考程序 III 动态规划解题的一般思路 动态规划解题的一般思路 动态规划解题的一般思路 最长上升子序列 问题描述 2、解题思路 2、解题思路 3、参考程序 3、参考程序 Help Jimmy 问题描述 问题描述 问题描述 2、解题思路 2、解题思路 2、解题思路 3、参考程序 3、参考程序 3、参考程序 3、参考程序 最长公共子序列 问题描述 2、解题思路 2、解题思路 3、参考程序 3、参考程序 陪审团的人选 问题描述 问题描述 2、解题思路 2、解题思路 2、解题思路 3、参考程序 3、参考程序 3、参考程序 3、参考程序 购物问题 问题描述 问题描述 2、解题思路 2、解题思路 3、参考程序 3、参考程序 3、参考程序 3、参考程序 3、参考程序 else //没找到 { if( y max )//离地面太高 return INFINITE; else return y; }//特殊情况处理完毕 int nLeftTime = y - aPlatform[i].h + x - aPlatform[i].Lx; int nRightTime = y - aPlatform[i].h + aPlatform[i].Rx - x; if( aLeftMinTime[i] == -1 )//还没有存储值 aLeftMinTime[i] = MinTime(i, true); if( aRightMinTime[i] == -1 ) aRightMinTime[i] = MinTime(i, false); nLeftTime += aLeftMinTime[i]; nRightTime += aRightMinTime[i]; if( nLeftTime nRightTime ) return nLeftTime; return nRightTime; } int main(void) { scanf(%d, t); for( int i = 0;i t; i ++ ) { memset(aLeftMinTime, -1, sizeof(aLeftMinTime)); memset(aRightMinTime, -1, sizeof(aRightMinTime)); scanf(%d%d%d%d, n, x, y, max); aPlatform[0].Lx = x; aPlatform[0].Rx = x;//长度为0的板子 aPlatform[0].h = y; for( int j = 1; j = n; j ++ ) scanf(%d%d%d, aPlatform[j].Lx, aPlatform[j].Rx, aPlatform[j].h); qsort(aPlatform, n+1, sizeof(Platform), MyCompare); printf(%d\n, MinTime(0, true)); } return 0; } 思考题：重新编写此程序，要求不使用递归函数 第十课 动态规划(II) 综合实践考核 1、问题描述 我们称序列Z = z1, z2, ..., zk 是序列X = x1, x2, ..., xm 的子序列当且仅当存在严格上升的序列 i1, i2, ..., ik ，使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = a, b, f, c 是X = a, b, c, f, b, c 的子序列。 现在给出两个序列X 和Y，你的任务是找到X 和Y 的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z 既是X 的子序列也是Y 的子序列。 输入数据 输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200 的字符串，表示两个序列。两个字符串之间由若干个空格隔开。 输出要求 对每组输入数据，输出一行，给出两个序列的最大公共子序列