动态规划解决LCS问题
一、LCS问题定义
给定两个序列(比如字符串)X 和 Y,我们需要找到一个最长的序列 Z,使得 Z 既是 X 的子序列,也是 Y 的子序列,并且 Z 的长度尽可能长。这里的“子序列”指的是可以通过删除原序列中的某些(也可能不删除)元素(但不改变剩余元素的相对顺序)而得到的序列。
二、动态规划解决LCS问题的步骤
1.定义子问题:
对于字符串 X 和 Y,定义 L[i][j] 为 X 的前 i 个字符(即 X[0…i-1])和 Y 的前 j 个字符(即 Y[0…j-1])之间的最长公共子序列的长度。
2.状态转移方程:
如果 X[i-1] == Y[j-1](即当前字符匹配),则 L[i][j] = L[i-1][j-1] + 1;可以将 X[i-1] 和 Y[j-1] 加入到之前的LCS中,从而增加LCS的长度。
如果 X[i-1] != Y[j-1](即当前字符不匹配),则 L[i][j] = max(L[i-1][j], L[i][j-1]);这里需要考虑两种情况:不包含 X[i-1] 的最长公共子序列(即 L[i-1][j]),和不包含 Y[j-1] 的最长公共子序列(即 L[i][j-1]),并取其中的较大值。
3.初始化边界条件:
当 i = 0 或 j = 0 时,即一个字符串为空时,最长公共子序列的长度为0;对于所有的 i 和 j,有 L[i][0] = 0 和 L[0][j] = 0。
4.填充DP表:
使用状态转移方程和边界条件来填充整个DP表 L。这通常通过两层嵌套循环来完成,外层循环遍历 X 的长度,内层循环遍历 Y 的长度。
5.读取结果:
最长公共子序列的长度存储在 L[m][n] 中,其中 m 和 n 分别是 X 和 Y 的长度。
(可选)构建LCS:
如果需要构建最长公共子序列本身,而不是仅仅计算其长度,可以通过回溯DP表来实现。这通常涉及到从 L[m][n] 开始,根据状态转移方程的决定(是匹配字符还是选择左边或上边的子问题解)来追踪回DP表的起点。