LCS

最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。

最长公共子序列问题存在最优子结构：这个问题可以分解成更小，更简单的“子问题”，这个子问题可以分成更多的子问题，因此整个问题就变得简单了。最长公共子序列问题的子问题的解是可以重复使用的，也就是说，更高级别的子问题通常会重用低级子问题的解。拥有这个两个属性的问题可以使用动态规划算法来解决，这样子问题的解就可以被储存起来，而不用重复计算。这个过程需要在一个表中储存同一级别的子问题的解，因此这个解可以被更高级的子问题使用。

LCS问题的子问题是什么？子问题和原问题有什么联系呢？

子问题：dp[i-1][j-1] dp[i][j-1] dp[i-1][j]

如果s1[i]==s2[j]，则dp[i][j]和dp[i-1][j-1]必然有直接的联系

否则，与 dp[i][j-1] dp[i-1][j]两个子问题有直接联系。

package main

import (
	"fmt"
)

func main() {
	fmt.Println(longestCommonSubsequence("xzyzzyx", "zxyyzxz"))
	fmt.Println(longestCommonSubsequence("MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCALLAAQANKESSSESFISRLLAIVAD", "MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCTLLAAQANKENSNESFISRLLAIVAG"))
}

func longestCommonSubsequence(text1 string, text2 string) int {
	// dp[i][j] 表示 text1长度为i的前缀 和 text2长度为j的前缀 的 LCS
	dp := make([][]int, len(text1)+1)
	for i := range dp {
		dp[i] = make([]int, len(text2)+1)
	}

	dp[1][1] = same(text1[0], text2[0])
	for i := 1; i < len(dp); i++ {
		for j := 1; j < len(dp[0]); j++ {
			dp[i][j] = max3(dp[i-1][j-1]+same(text1[i-1], text2[j-1]), dp[i-1][j], dp[i][j-1])
		}
	}
	return dp[len(dp)-1][len(dp[0])-1]
}

// 两个字符相同时返回1，否则返回0
func same(a, b uint8) int {
	if a == b {
		return 1
	}
	return 0
}

func max3(a, b, c int) int {
	return max(max(a, b), c)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}