最长公共子序列（LCS）问题的核心是先通过动态规划计算两个序列的最长公共长度，再通过回溯从状态表中还原出具体的公共子序列。在Go语言实现回溯逻辑时，索引一致性是最容易出错的环节，稍不注意就会导致输出的序列缺失字符或者出现多余字符。
LCS动态规划的基础逻辑
动态规划求解LCS时，通常会定义二维数组dp[i][j]表示第一个序列前i个字符和第二个序列前j个字符的最长公共子序列长度。状态转移规则如下：
- 如果当前两个序列的字符相等，
dp[i][j] = dp[i-1][j-1] + 1 - 如果字符不相等，
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
这里需要注意，序列的索引通常从0开始，而dp数组的索引从1开始，这是后续回溯时索引不一致的主要来源。
回溯过程的索引一致性问题
回溯的起点是dp[len(seq1)][len(seq2)]的位置，需要从后往前遍历两个序列。常见的索引错误有两种：
错误1：序列索引和dp数组索引直接对应
很多开发者会直接用dp的i、j索引去取序列的字符，比如seq1[i] == seq2[j]，但实际上dp的i对应seq1的第i-1个字符，直接取就会越界或者取到错误字符。
错误2：回溯方向不匹配状态转移逻辑
当dp[i][j]等于dp[i-1][j]或者dp[i][j-1]时，回溯方向需要和状态转移时的选择一致，如果方向混乱，就会导致索引偏移，最终输出的序列错误。
Go语言正确实现示例
下面是完整的Go语言实现代码，包含动态规划计算和回溯输出，所有索引处理都保证了一致性：
package main
import (
"fmt"
)
// 计算最长公共子序列长度并生成dp数组
func lcsDP(seq1, seq2 string) [][]int {
m, n := len(seq1), len(seq2)
// dp数组多一行一列，方便处理边界情况
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// 填充dp数组
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
// 注意这里seq的索引是i-1和j-1，和dp的i、j对应
if seq1[i-1] == seq2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
if dp[i-1][j] > dp[i][j-1] {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = dp[i][j-1]
}
}
}
}
return dp
}
// 回溯获取最长公共子序列
func backtrackLCS(seq1, seq2 string, dp [][]int) string {
m, n := len(seq1), len(seq2)
i, j := m, n
var res []byte
// 从dp数组的右下角开始回溯
for i > 0 && j > 0 {
// 字符相等时，说明该字符属于LCS，加入结果，同时i、j各减1
// 这里seq的索引是i-1和j-1，和dp的i、j对应，保证索引一致
if seq1[i-1] == seq2[j-1] {
res = append(res, seq1[i-1])
i--
j--
} else {
// 根据dp数组的值选择回溯方向，和状态转移逻辑一致
if dp[i-1][j] > dp[i][j-1] {
i--
} else {
j--
}
}
}
// 回溯得到的是逆序结果，需要反转
for l, r := 0, len(res)-1; l < r; l, r = l+1, r-1 {
res[l], res[r] = res[r], res[l]
}
return string(res)
}
func main() {
seq1 := "abcde"
seq2 := "ace"
dp := lcsDP(seq1, seq2)
lcs := backtrackLCS(seq1, seq2, dp)
fmt.Printf("最长公共子序列是：%sn", lcs)
fmt.Printf("最长公共子序列长度是：%dn", dp[len(seq1)][len(seq2)])
}
关键注意点总结
要保证回溯时的索引一致性，只需要记住两个核心原则：
- dp数组的
i对应第一个序列的i-1索引，j对应第二个序列的j-1索引，取字符时永远做减1处理 - 回溯的方向必须和动态规划时的状态转移方向完全匹配，不能凭感觉选择移动i还是j
按照这两个原则实现，就可以避免Go语言中LCS回溯算法的索引一致性问题，得到正确的结果。