精选优质文档-倾情为你奉上动态规划解最长公共子序列 一、 问题描述与分析经常遇到一些复杂的问题，有时我们将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。由于分解到的子问题往往不是独立的，用一个表来记录所有已解决的子问题的答案，这样就得到了原问题的解，这就是动态规划法的基本思想。一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z即是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。在公共子序列中长度最长的则是最长公共子序列。穷举搜索法是最容易想到的解题算法。对X的所有子序列，检查它是否也是Y的子序列，从而确定它是否是X和Y的公共子序列。并且在检查过程中记录最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。事实上，最长公共子序列问题具有最优子结构的结构性质。二、 算法设计1. 最长公共子序列的结构设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk
