最长公共子序列

动态规划

说明

相等字符使答案加一，否则取跳过任一字符的较大值；时间 O(nm)。

分析

dp[i][j] 考虑两个字符串各自的前 i、j 个字符。末尾字符相同就接在更短前缀的答案后；不同则分别跳过一侧末尾，取较大者。

图解推演

abcde 与 ace 可保留 a、c、e，跳过 b、d，长度 3。末字符相同会把对角线状态延长；不同时沿上方或左方选较大值，因为至少要舍弃一个末字符。只存长度无法直接输出序列，重建需要记录或回查转移方向。

查看图表代码

适用前提与边界

子序列允许不连续，示例按 UTF-8 字节比较；按字符语义处理中文时应改成 rune。

示例输入与调用

fmt.Println(LCS("abcde", "ace"))

运行输出

3

完整 Go 示例

package main

import "fmt"

func LCS(a, b string) int {
	dp := make([][]int, len(a)+1)
	for i := range dp {
		dp[i] = make([]int, len(b)+1)
	}
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			if a[i-1] == b[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[len(a)][len(b)]
}

func main() {
	fmt.Println(LCS("abcde", "ace"))
}