Skip to main content

1143. Longest Common Subsequence

分析

dp 分解子问题
dp[i][j] 定义为 text1 [i, len - 1] 与 text2 [j, len - 1] 的 LCS

if text1[i] == text2[j] => dp[i][j] = dp[i+1][j+1] + 1
else max(dp[i+1][j], dp[i][j+1])

Pasted image 20220418130304.png

题解

自顶向下 dfs + cache

func longestCommonSubsequence(text1 string, text2 string) int {

var dfs func(i, j int) int
memo := map[[2]int]int{}

dfs = func(i, j int) int {
if i >= len(text1) || j >= len(text2) {
return 0
}
cached, ok := memo[[2]int{i, j}]
if ok {
return cached
}
var temp int
if text1[i] == text2[j] {
temp = dfs(i + 1, j + 1) + 1

} else {
temp = max(dfs(i + 1, j), dfs(i, j + 1))
}
memo[[2]int{i, j}] = temp
return temp
}

return dfs(0, 0)
}

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

自底向上

func longestCommonSubsequence(text1 string, text2 string) int {
m, n := len(text1), len(text2)
dp := make([][]int, m + 1)
for i := 0; i < m + 1; i++ {
dp[i] = make([]int, n + 1)
}

for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if text1[i] == text2[j] {
dp[i][j] = dp[i+1][j+1] + 1
} else {
dp[i][j] = max(dp[i+1][j], dp[ i][j+1])
}
}
}
return dp[0][0]
}

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