问题
https://leetcode-cn.com/problems/longest-common-subsequence
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
解法
一个最直接简单的方法是穷举比较，但性能显然很差，时间复杂度也很高。
还有一个思路，细化到两个字符串的每个字符。
定义一个函数，func dp (s1 string,idx1 int,s2 string,idx2 int) int {...}
如果字符串 s1 中的 idx1 位置的字符与字符串 s2 中 idx2 中的字符相同，则这两个字符后面的公共子序列的长度为 1+ dp(s1,idx1+1,s2,idx2+1)。
如果字符串 s1 中的 idx1 位置的字符与字符串 s2 中 idx2 中的字符不同，则这两个字符后面的公共子序列的长度为 0+ dp(s1,idx1+1,s2,idx2)、 0+ dp(s1,idx1,s2,idx2+1)、 0+ dp(s1,idx1+1,s2,idx2+1) 中的一个。由于题目需要找最大的子序列长度，而 dp(s1,idx1+1,s2,idx2+1) <= dp(s1,idx1+1,s2,idx2) 且 dp(s1,idx1+1,s2,idx2+1) <= dp(s1,idx1,s2,idx2+1) （可比较的字符越多，最大子序列长度越大），那么这种情况下公共子序列的长度为 max(dp(s1,idx1+1,s2,idx2),dp(s1,idx1,s2,idx2+1))。
上面的流程构成一个递归，开始情形为 dp(s1,0,s2,0)，最终情形为 dp(s1,len(s1),s2,len(s2))。最终情况结果肯定为0。
于是有下面的解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package main
import (
"fmt"
)
func getMaxCommonseqLen(s1 string, s2 string) int {
memo := [][]int{}
for i := 0; i < len(s1); i++ {
tmp := []int{}
for j := 0; j < len(s2); j++ {
tmp = append(tmp, -1)
}
memo = append(memo, tmp)
}
return dp(s1, 0, s2, 0, &memo)
}
func dp(s1 string, idx1 int, s2 string, idx2 int, memo *[][]int) int {
if idx1 == len(s1) || idx2 == len(s2) {
// 到头了
return 0
}
if (*memo)[idx1][idx2] != -1 {
return (*memo)[idx1][idx2]
}
if s1[idx1] == s2[idx2] {
(*memo)[idx1][idx2] = 1 + dp(s1, idx1+1, s2, idx2+1, memo)
} else {
r1 := dp(s1, idx1+1, s2, idx2, memo)
r2 := dp(s1, idx1, s2, idx2+1, memo)
if r1 > r2 {
(*memo)[idx1][idx2] = r1
} else {
(*memo)[idx1][idx2] = r2
}
}
return (*memo)[idx1][idx2]
}
func main() {
s1 := "ilikehuaweibest!"
s2 := "doulikechina?"
s3 := "huaweilocatesinchina"
println("s1:" + s1)
println("s2:" + s2)
println("s3:" + s3)
r1 := getMaxCommonseqLen(s1, s2)
fmt.Printf("s1,s2 result:%v \n", r1)
r2 := getMaxCommonseqLen(s1, s3)
fmt.Printf("s1,s3 result:%v \n", r2)
}
输出结果：
1
2
3
4
5
s1:ilikehuaweibest!
s2:doulikechina?
s3:huaweilocatesinchina
s1,s2 result:6
s1,s3 result:8
这个解法用到了“备忘录”，为了标记中间结果，避免重复的计算。
上面的解法，实际上是动态规划的问题，通过把问题缩小到最小可解范围，一步步递推得到大范围的结果。