题目链接: 902. 最短编辑距离
主体思路
看老师的视频吧,已经讲得很清楚了
注意细节
- dp空间需要预处理
for i := 0; i <= n; i++ { dp[i][0] = i }
for j := 0; j <= m; j++ { dp[0][j] = j }
//不要写成了
for i := 0; i <= n; i++ { dp[i][0] = 1 }
for j := 0; j <= m; j++ { dp[0][j] = 1 }
基础写法: 二维DP + 二重for
package main
import "fmt"
func cal(n, m int, A, B string) int {
var (
min = func(i, j int) int { if i < j { return i }; return j };
dp = make([][]int, n + 1)
)
for i := range dp { dp[i] = make([]int, m + 1) }
for i := 0; i <= n; i++ { dp[i][0] = i }
for j := 0; j <= m; j++ { dp[0][j] = j }
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
if A[i] == B[j] {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
} else {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
}
}
}
return dp[n][m]
}
func main() {
var (
ans int
n, m int
tmpA, tmpB string
A, B = string(" "), string(" ")
)
fmt.Scanf("%d", &n)
fmt.Scanf("%s", &tmpA)
fmt.Scanf("%d", &m)
fmt.Scanf("%s", &tmpB)
A += tmpA
B += tmpB
ans = cal(n, m, A, B)
fmt.Println(ans)
}