主体思路
关键还是状态转移方程要怎么写
直接想的话,是要考虑以下四种情况:
都不拿字符串A、字符串B的最后字符: dp[i - 1][j - 1]
都拿字符串A、字符串B的最后字符: dp[i - 1][j - 1] + 1
拿字符串A的最后字符,不拿字符串B的最后字符: dp[i][j - 1]
不拿字符串A的最后字符,拿字符串B的最后字符: dp[i][j - 1]
这里可以看到在分状态时要做到不重不漏
同时,在算max反而不用太但心重复算,因为这样,可以不管 dp[i - 1][j - 1]
这情况
注意细节
【go语法细节】小心处理string
1. 一般写法:二维DP + 二重for
package main
import "fmt"
func cal(N, M int, A, B string) int {
var (
dp = make([][]int, N + 1)
max = func(i, j int) int { if i > j { return i }; return j }
)
for i := range dp { dp[i] = make([]int, M + 1) }
for i := 1; i <= N; i++ {
for j := 1; j <= M; j++ {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
if A[i] == B[j] { dp[i][j] = max(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 %d", &N, &M)
fmt.Scanf("%s", &tmpA)
fmt.Scanf("%s", &tmpB)
A += tmpA
B += tmpB
ans = cal(N, M, A, B)
fmt.Println(ans)
}
2. 小小优化:二维DP + 二重for + 滚动数组
package main
import "fmt"
func cal(N, M int, A, B string) int {
var (
dp = make([][]int, 2)
max = func(i, j int) int { if i > j { return i }; return j }
)
for i := range dp { dp[i] = make([]int, M + 1) }
for i := 1; i <= N; i++ {
for j := 1; j <= M; j++ {
dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[i & 1][j - 1])
if A[i] == B[j] { dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j - 1] + 1) }
}
}
return dp[N & 1][M]
}
func main() {
var (
ans int
N, M int
tmpA, tmpB string
A, B = string(" "), string(" ")
)
fmt.Scanf("%d %d", &N, &M)
fmt.Scanf("%s", &tmpA)
fmt.Scanf("%s", &tmpB)
A += tmpA
B += tmpB
ans = cal(N, M, A, B)
fmt.Println(ans)
}