实验二动态规划算法 实验 二 动态规划算法 基本题一：最长公共子序列问题 一、实验目的与要求 1 1 、熟悉最长公共子序列问题的算法； 2 2 、初步掌握动态规划算法； 二、实验题 若给定序列 X=x1,x2, ,xm ，则另一序列 Z=z1,z2, ,zk ，是 X X 的子序列是指存在一个严格递增下标序列 i1,i2, ,ik 使得对于所有 j=1,2, k ,k 有： zj=xij 。例如，序列 Z=B ，C C ，D D ， B 是序列 X=A ，B B ，C C ，B B ，D D ，A A ， B 的子序列，相应的递增下标序列为 2 ，3 3 ，5 5 ， 7 。 给定 2 2 个序列 X X 和 和 Y Y ，当另一序列 Z Z 既是 X X 的子序列又是 Y Y 的子序列时，称 Z Z是序列 X X 和 和 Y Y 的公共子序列。 给定 2 2 个序列 X=x1,x2, ,xm和 和 Y=y1,y2, ,yn ，找出 X X 和 和 Y Y 的最长公共子序列。
