最长公共子序列-木庄网络博客

本文摘自网络，作者，侵删。

最长公共子序列（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 类型用途更广。

本文来自：简书

感谢作者：追风骚年

查看原文：最长公共子序列