09-算法设计
4.3.2 算法设计
最长公共子序列问题满足动态规划的最优子结构性质，可以自底向上逐步得到最优解。
（1）确定合适的数据结构
采用二维数组c[][]来记录最长公共子序列的长度，二维数组b[][]来记录最长公共子序列的长度的来源，以便算法结束时倒推求解得到该最长公共子序列。
（2）初始化
输入两个字符串s1、s2，初始化c[][]第一行第一列元素为0。
（3）循环阶段
- i = 1：s1[0]与s2[j−1]比较，j=1，2，3，…，len2。
如果s1[0]=s2[j−1]，c[i][j] = c[i−1][j−1]+1；并记录最优策略来源b[i][j]=1；
如果s1[0] ≠s2[j−1]，则公共子序列的长度为c[i][j−1]和c[i−1][j]中的最大值，如果c[i][j−1]
c[i−1][j]，则c[i][j]=c[i][j−1]，最优策略来源b[i][j]=2；否则c[i][j]= c[i−1][j]，最优策略来源b[i][j]=3。
- i = 2：s1[1]与s2[j−1]比较，j=1，2，3，…，len2。
- 以此类推，直到i > len1时，算法结束，这时c[len1][len2]就是最长公共序列的长度。
（4）构造最优解
根据最优决策信息数组b[][]递归构造最优解，即输出最长公共子序列。因为我们在求最长公共子序列长度c[i][j]的过程中，用b[i][j]记录了c[i][j]的来源，那么就可以根据b[i][j]数组倒推最优解。
如果b[i][j]=1，说明s1[i−1]=s2[j−1]，那么就可以递归求解print(i−1, j−1)；然后输出s1[i−1]。
注意： 如果先输出，后递归求解print(i−1,j−1)，则输出的结果是倒序。
如果b[i][j]=2，说明s1[i−1]≠s2[j−1]且最优解来源于c[i][j]=c[i][j−1]，递归求解print(i, j−1)。
如果b[i][j]=3，说明s1[i−1]≠s2[j−1]且最优解来源于c[i][j]=c[i−1][j]，递归求解print(i−1, j)。当i==0 || j==0时，递归结束。