跳转至

LC1143 - 最长公共子序列

LongestCommonSubsequence.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
package DP2

func longestCommonSubsequence(text1 string, text2 string) int {
    size1, size2 := len(text1), len(text2)
    dp := make([][]int, size1+1)
    for i := 0; i < size1+1; i++ {
        dp[i] = make([]int, size2+1)
    }
    for i := 1; i <= size1; i++ {
        for j := 1; j <= size2; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[size1][size2]
}