package main import "fmt" func solution(str1, str2 string) int { dp := make([][]int, len(str1)+1) for i := range dp { dp[i] = make([]int, len(str2)+1) } for i, ch1 := range str1 { for j, ch2 := range str2 { if ch1 == ch2 { dp[i+1][j+1] = dp[i][j] + 1 } else { dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]) } } } return dp[len(str1)][len(str2)] } func max(a, b int) int { if a > b { return a } return b } /* * 输入: abcde ace 输出:3 解释:最长公共子序列是 "ace" ,它的长度为 3 。 */ func main() { var str1len int var str2len int fmt.Scanln(&str1len) fmt.Scanln(&str2len) var str1 string var str2 string fmt.Scanln(&str1) fmt.Scanln(&str2) fmt.Println(solution(str1, str2)) }