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) } //初始化dp for i := 1; i < len(dp); i++ { dp[i][0] = dp[i-1][0] + 1 } for i := 1; i < len(dp[0]); i++ { dp[0][i] = dp[0][i-1] + 1 } //开始dp for i := 0; i < len(str1); i++ { for j := 0; j < len(str2); j++ { if str1[i] == str2[j] { dp[i+1][j+1] = dp[i][j] } else { dp[i+1][j+1] = min(dp[i][j], min(dp[i+1][j], dp[i][j+1])) + 1 } } } return dp[len(str1)][len(str2)] } func min(a, b int) int { if a > b { return b } return a } /* * //结果3 str1 := "abcdefg" str2 := "abcd" //结果3 str1 := "horse" str2 := "ros" */ func main() { var str1, str2 string fmt.Scanln(&str1) fmt.Scanln(&str2) fmt.Println(solution(str1, str2)) }