刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/longest-common-subsequence/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

思路

子序列这类问题还是挺容易能想到动态规划的，毕竟如果用字符串匹配的方式就太麻烦了，时间复杂度压不住啊

首先是dp定义

此dp数组定义相对简单些，定义是为了往小处拆解问题，并且保证无后效性。这里我们往小处拆解的话，就可以从两个字符串只含一个字符、两个字符、...等等这样的方式，来一个个增加字符，这样也就容易得到一个递进的逻辑关系，有助于写出状态方程。所以
dp[i][j]含义定为 text1 中 [0,i] 子串 和 text2 中 [0,j] 子串的最长公共子序列长度

初始化条件

当 text1 或者 text2 的子串长度为0时，他们的公共子序列一定是空，所以，i=0 或者 j=0 这一行一列均为0。（恰好找不到结果时，需要返回的也就是0）

状态转移方程

在 text1 、 text2 增长过程中

• 如果此时下标为 i 、 j 的末尾的字符相等，那么，公共子序列长度就相当于是在 i-1、 j-1 的基础上 +1。即dp[i][j] = dp[i-1][j-1]+1
• 否则的话，则与text1 少一个字符或者 text2 少一个字符没有区别。即 dp[i][j] = dp[i][j-1] 或者 dp[i][j] = dp[i-1][j], 取其中较大的即可。

至此，上代码

代码

func longestCommonSubsequence(text1 string, text2 string) int {
    n1 := len(text1)
    n2 := len(text2)
    // 别忘了为0的情况，所以要多一行/列
    dp := make([][]int, n1+1)
    for i:=0; i<=n1; i++ {
        dp[i] = make([]int, n2+1)
    }
    // 从1开始，0行为初始条件，无需遍历
    for i:=1; i<=n1; i++ {
        for j:=1; j<=n2; j++ {
            // 因为dp数组下标从1开始，此时text1、text2末尾字符下标需 -1
            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[n1][n2]
}

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