最长公共子序列（Longest Common Subsequence，简称 LCS）是非常经典的动态规划题目。
通常有两种方式，一个是自顶向下的递归写法，一个是自底向上的 dp table 写法，这里我在使用递归时，发现 golang 的一个问题，如果在函数内部定义个函数，那么内部函数的内部是无法访问到内部函数名。
例如：
func lcs(s1, s2 string) {
dp := func(i, j int) int {
...
return dp(i, j-1) // 这里是无法访问到 dp 函数名
}
}
由于 golang 的严谨性，函数在使用的过程中，必须先定义，所以如下修改：
func lcs(s1, s2 string) {
var dp func(i, j int) int
dp = func(i, j int) int {
// ...
return dp(i, j-1) // success
}
}
虽然看起来有点蹩脚，但是只有这样才能通过编译。通过声明和赋值放一起，这样固然是舒服和便携，但编译器都是先执行等号右边再去赋值给左边，在右边的函数内部，还并不知道左边的变量名。
LCS 完整代码
- 递归版本
func lcs(text1, text2 string) int {
cache := make([][]int, len(text1))
for idx := range cache {
cache[idx] = make([]int, len(text2))
}
var dp func(i, j int) int
dp = func(i, j int) int {
if i == -1 {
return 0
}
if j == -1 {
return 0
}
if cache[i][j] != 0 {
return cache[i][j]
}
if text1[i] == text2[j] {
cache[i][j] = dp(i-1, j-1) + 1
} else {
d1 := dp(i, j-1)
d2 := dp(i-1, j)
if d1 > d2 {
cache[i][j] = d1
} else {
cache[i][j] = d2
}
}
return cache[i][j]
}
return dp(len(text1)-1, len(text2)-1)
}
这里也取了一个巧，将 i，j == -1 的判断放上面，因为如果先走 cache 的话，就可能遇到越界的操作了。
- 打表版本
func lcs(text1, text2 string) int {
m, n := len(text1), len(text2)
dp := make([][]int, m+1)
for idx := range dp {
dp[idx] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if text1[i-1] == text2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
}
}
}
return dp[m][n]
}
func max(n1, n2 int) int {
if n1 > n2 {
return n1
}
return n2
}
这里不得不吐槽一下 math 包中的 max 函数居然是 float64 类型的，实际应用中反而 int 类型用途更广。
有疑问加站长微信联系（非本文作者）
