文心一言 VS 讯飞星火 VS chatgpt （206）-- 算法导论15.4 3题
三、设计 LCS-LENGTH的带备忘的版本，运行时间为O(mn)。需要写代码的时候，请用go语言。
文心一言，代码正常运行：
LCS-LENGTH（Longest Common Subsequence Length）问题的带备忘的版本通常指的是使用动态规划（Dynamic Programming, DP）和备忘录（Memoization）来优化算法性能，避免重复计算。通过维护一个表（即“备忘录”）来存储已经计算过的子问题的解，从而在解决新问题时可以直接查找已存储的结果，而不是重新计算。
以下是使用Go语言实现的一个带备忘的LCS-LENGTH算法的示例。在这个示例中，lcsLength 函数计算两个字符串的最长公共子序列长度，并且使用一个二维数组 memo 来存储子问题的解，其中 memo[i][j] 存储的是 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列长度。
package main
import (
"fmt"
)
func lcsLength(str1, str2 string) int {
m, n := len(str1), len(str2)
memo := make([][]int, m+1)
for i := range memo {
memo[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if str1[i-1] == str2[j-1] {
memo[i][j] = memo[i-1][j-1] + 1
} else {
memo[i][j] = max(memo[i-1][j], memo[i][j-1])
}
}
}
return memo[m][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
str1 := "ABCDEFG"
str2 := "XYZABCDEFGHIJKL"
length := lcsLength(str1, str2)
fmt.Printf("The length of the Longest Common Subsequence is: %d\n", length)
}
在这个实现中，lcsLength 函数首先初始化一个 (m+1) x (n+1) 的二维数组 memo，其中 m 和 n 分别是两个输入字符串 str1 和 str2 的长度。然后，它使用两个嵌套的循环来遍历 str1 和 str2 的所有字符组合。
如果 str1 的第 i 个字符和 str2 的第 j 个字符相同，则最长公共子序列的长度加一，即 memo[i][j] = memo[i-1][j-1] + 1。如果不同，则最长公共子序列的长度是去掉 str1 的第 i 个字符后的最长公共子序列和去掉 str2 的第 j 个字符后的最长公共子序列中的较大值，即 memo[i][j] = max(memo[i-1][j], memo[i][j-1])。
最后，函数返回 memo[m][n]，即两个字符串的最长公共子序列的长度。
请注意，这个实现的时间复杂度是 O(mn)，其中 m 和 n 分别是两个输入字符串的长度。这是因为我们需要填充一个 m x n 的表，而每个表项的计算时间是常数时间。
讯飞星火，代码正常运行：
在Go语言中，我们可以使用动态规划来解决这个问题。以下是实现LCS-LENGTH的带备忘的版本的代码：
package main
import "fmt"
func max(a, b int) int {
if a > b {
return a
}
return b
}
func lcsLength(X, Y []int) int {
m := len(X)
n := len(Y)
c := make([][]int, m+1)
for i := range c {
c[i] = make([]int, n+1)
}
for i := 0; i <= m; i++ {
for j := 0; j <= n; j++ {
if i == 0 || j == 0 {
c[i][j] = 0
} else if X[i-1] == Y[j-1] {
c[i][j] = c[i-1][j-1] + 1
} else {
c[i][j] = max(c[i-1][j], c[i][j-1])
}
}
}
return c[m][n]
}
func main() {
X := []int{1, 3, 4, 5, 6, 7, 7, 8}
Y := []int{2, 3, 5, 6, 7, 8, 9, 10}
fmt.Println("Length of LCS is", lcsLength(X, Y))
}
在这个程序中，我们首先定义了一个二维数组c，用于存储子问题的解。然后，我们遍历两个输入序列，如果当前位置的元素相同，则该位置的LCS长度为左上角元素的LCS长度加一；否则，该位置的LCS长度为左边元素和上边元素中较大的那个LCS长度。最后，右下角的元素就是整个序列的LCS长度。
360智脑，代码不能运行：
以下是一个使用Go语言实现的LCS-Length带备忘的版本：
package main
func lcsLength(memo map[int][int]int, X string, Y string, m int, n int) int {
if m == 0 || n == 0 {
return 0
}
if v, ok := memo[m][n]; ok {
return v
}
if X[m-1] == Y[n-1] {
memo[m][n] = lcsLength(memo, X, Y, m-1, n-1) + 1
} else {
memo[m][n] = max(lcsLength(memo, X, Y, m-1, n), lcsLength(memo, X, Y, m, n-1))
}
return memo[m][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
X := "ABCBDAB"
Y := "BDCAB"
memo := make(map[int][int]int)
m := len(X)
n := len(Y)
fmt.Println(lcsLength(memo, X, Y, m, n))
}
在这个代码中，我们使用了一个备忘录（memo）来存储之前计算过的LCS长度。当我们计算LCS长度时，我们首先检查备忘录中是否已经有这个值。如果有，我们就直接返回它；如果没有，我们就计算它，并将其存储在备忘录中。
这个算法的运行时间为O(mn)，因为我们在计算LCS长度时，最多需要遍历X和Y字符串的每个字符。
智谱清言，代码正常运行：
为了设计一个运行时间为O(mn)的LCS-LENGTH算法，我们可以使用动态规划(DP)技术，并辅以带备忘的递归方法来避免重复计算。在下面给出的Go语言代码中，我们将计算两个字符串
str1
和
str2
的最长公共子序列的长度。
package main
import (
"fmt"
)
// LCSLength 计算两个字符串的最长公共子序列的长度
// 使用带备忘的递归方法
func LCSLength(str1, str2 string) int {
// 创建一个二维切片来保存子问题的结果
// dp[i][j] 表示str1的前i个字符与str2的前j个字符的LCS长度
dp := make([][]int, len(str1)+1)
for i := range dp {
dp[i] = make([]int, len(str2)+1)
}
// 初始化dp数组
for i := 0; i <= len(str1); i++ {
for j := 0; j <= len(str2); j++ {
if i == 0 || j == 0 {
dp[i][j] = 0
}
}
}
// 递归计算LCS长度，同时更新dp数组
return recursiveLCSLength(str1, str2, 0, 0, dp)
}
// recursiveLCSLength 递归计算最长公共子序列的长度
// 同时更新dp数组以避免重复计算
func recursiveLCSLength(str1, str2 string, i, j int, dp [][]int) int {
// 检查是否已经计算过这个子问题
if dp[i][j] != 0 {
return dp[i][j]
}
// 如果i或j为0，那么LCS长度为0
if i == 0 || j == 0 {
dp[i][j] = 0
return 0
}
// 如果str1[i-1] == str2[j-1]，那么当前字符是LCS的一部分
if str1[i-1] == str2[j-1] {
dp[i][j] = 1 + recursiveLCSLength(str1, str2, i-1, j-1, dp)
} else {
// 否则，取左侧或上侧的LCS长度中的较大值
dp[i][j] = max(recursiveLCSLength(str1, str2, i-1, j, dp), recursiveLCSLength(str1, str2, i, j-1, dp))
}
return dp[i][j]
}
// max 返回两个整数中的较大值
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
str1 := "ABCBDAB"
str2 := "BDCAB"
fmt.Println("The length of LCS is:", LCSLength(str1, str2))
}
这段代码定义了一个
LCSLength
函数，它使用一个二维切片
dp
来存储子问题的解，并且通过递归函数
recursiveLCSLength
来计算最长公共子序列的长度。递归函数会在每次需要计算相同子问题时，检查是否已经在
dp
中存储了结果，以避免重复计算。
main
函数中给出了一个例子，计算字符串"ABCBDAB"和"BDCAB"的最长公共子序列的长度，并打印结果。
天工，代码正常运行：
Certainly! Below is an implementation of the LCS problem with memoization in Go that runs in O(mn) time, where m and n are the lengths of the two input strings. This implementation uses a二维数组 to store the results of subproblems, avoiding重复计算.
package main
import "fmt"
// LCSMemo computes the length of the longest common subsequence between X and Y using memoization.
func LCSMemo(X, Y string) int {
m, n := len(X), len(Y)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if X[i-1] == Y[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[m][n]
}
// max returns the larger of two integers.
func max(a, b int) int {
if a >= b {
return a
}
return b
}
func main() {
X := "AGGTAB"
Y := "GXTXAYB"
length := LCSMemo(X, Y)
fmt.Printf("Length of LCS: %d\n", length)
}
To use this code, simply run it with the Go runtime and it will output the length of the longest common subsequence between the two given strings. The
max
function is used to handle the comparison of integers, as
int
in Go does not guarantee a specific signedness.
灵小智，代码正常运行：
下面是用Go语言编写的带备忘录的最长公共子序列（LCS）问题的代码示例：
package main
import (
"fmt"
)
func max(a, b int) int {
if a > b {
return a
}
return b
}
func lcsLengthMemoized(X, Y string, m, n int, memo [][]int) int {
if m == 0 || n == 0 {
return 0
}
if memo[m][n] != -1 {
return memo[m][n]
}
if X[m-1] == Y[n-1] {
memo[m][n] = 1 + lcsLengthMemoized(X, Y, m-1, n-1, memo)
return memo[m][n]
}
memo[m][n] = max(lcsLengthMemoized(X, Y, m-1, n, memo), lcsLengthMemoized(X, Y, m, n-1, memo))
return memo[m][n]
}
func lcsLength(X, Y string) int {
m := len(X)
n := len(Y)
memo := make([][]int, m+1)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
return lcsLengthMemoized(X, Y, m, n, memo)
}
func main() {
X := "ABCBDAB"
Y := "BDCAB"
fmt.Printf("Length of LCS: %d\n", lcsLength(X, Y))
}
在这个代码中，我们使用了备忘录（memo）来保存已计算过的子问题的结果，以避免重复计算。通过将已计算过的结果存储在备忘录中，我们可以将算法的运行时间从指数级别降低到线性级别。这样，算法的运行时间为O(mn)，其中m和n分别是字符串X和Y的长度。
以上是用Go语言编写的带备忘录的LCS问题的代码示例，希望对你有帮助！
chatgpt，代码正常运行：
当设计LCS-LENGTH函数的带备忘的版本时，可以使用动态规划的思想。下面是用Go语言实现的代码：
package main
import (
"fmt"
)
func lcsLengthMemo(X, Y string) int {
m := len(X)
n := len(Y)
// 创建并初始化备忘录
memo := make([][]int, m+1)
for i := 0; i <= m; i++ {
memo[i] = make([]int, n+1)
for j := 0; j <= n; j++ {
memo[i][j] = -1
}
}
var lcs func(int, int) int
lcs = func(i, j int) int {
if memo[i][j] != -1 { // 如果已经计算过，直接返回备忘录中的值
return memo[i][j]
}
if i == 0 || j == 0 { // 边界条件，其中一个字符串为空
memo[i][j] = 0
return 0
}
if X[i-1] == Y[j-1] { // 当前字符匹配成功，继续向前匹配
memo[i][j] = lcs(i-1, j-1) + 1
return memo[i][j]
} else { // 当前字符不匹配，取两种情况下的最大值
left := lcs(i-1, j)
top := lcs(i, j-1)
if left > top {
memo[i][j] = left
} else {
memo[i][j] = top
}
return memo[i][j]
}
}
return lcs(m, n)
}
func main() {
X := "ABCBDAB"
Y := "BDCAB"
fmt.Println("LCS长度:", lcsLengthMemo(X, Y))
}
该代码使用了备忘录来存储已经计算过的子问题的结果，避免重复计算。通过递归方式进行动态规划，从后往前匹配字符串，并记录最长公共子序列的长度。运行时间复杂度为O(mn)。
kimi，代码正常运行：
在 Go 语言中，设计一个带有备忘（Memoization）的 LCS-LENGTH 版本，可以通过创建一个额外的二维切片来存储已经计算过的子问题的解。这样，当我们需要计算一个新的子问题时，我们首先检查这个解是否已经被计算过。如果已经计算过，我们可以直接使用这个解，而不需要重新计算，从而提高算法的效率。
以下是带有备忘的 LCS-LENGTH 函数的 Go 语言实现：
package main
import (
"fmt"
)
// LCS-LENGTH 函数计算两个序列的最长公共子序列的长度
func LCSLength(x, y []int) int {
m, n := len(x), len(y)
memo := make([][]int, m+1)
for i := range memo {
memo[i] = make([]int, n+1)
}
return lcsLengthMemo(x, y, m, n, memo)
}
// lcsLengthMemo 是 LCS-LENGTH 的递归实现，带有备忘
func lcsLengthMemo(x, y []int, m, n int, memo [][]int) int {
if m == 0 || n == 0 {
return 0
}
// 检查解是否已经在备忘数组中
if memo[m][n] != 0 {
return memo[m][n]
}
if x[m-1] == y[n-1] {
// 如果当前元素相同，递归计算去掉这两个元素后的子问题的解
memo[m][n] = 1 + lcsLengthMemo(x, y, m-1, n-1, memo)
} else {
// 如果当前元素不同，分别计算两种情况的解，并取最大值
memo[m][n] = max(
lcsLengthMemo(x, y, m-1, n, memo),
lcsLengthMemo(x, y, m, n-1, memo),
)
}
return memo[m][n]
}
// max 返回两个整数中的最大值
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
x := []int{1, 0, 0, 1, 0, 1, 0, 1}
y := []int{0, 1, 0, 1, 1, 0, 1, 1, 0}
length := LCSLength(x, y)
fmt.Printf("Length of LCS: %d\n", length)
}
在这个实现中，
LCSLength
函数是用户调用的接口，它初始化备忘数组并调用
lcsLengthMemo
函数。
lcsLengthMemo
函数是递归实现，它使用备忘数组来避免重复计算。这个算法的时间复杂度是 O(m * n)，因为每个子问题只计算一次，并且我们使用 O(m * n) 的空间来存储备忘数组。
混元，代码正常运行：
带备忘的 LCS-LENGTH 算法是一种动态规划方法，用于计算两个字符串的最长公共子序列的长度。以下是使用 Go 语言实现的带备忘的 LCS-LENGTH 算法：
package main
import (
"fmt"
)
func lcsLengthMemo(x, y string, m, n int, memo [][]int) int {
if m == 0 || n == 0 {
return 0
}
if memo[m][n] != -1 {
return memo[m][n]
}
if x[m-1] == y[n-1] {
memo[m][n] = 1 + lcsLengthMemo(x, y, m-1, n-1, memo)
} else {
memo[m][n] = max(lcsLengthMemo(x, y, m-1, n, memo), lcsLengthMemo(x, y, m, n-1, memo))
}
return memo[m][n]
}
func lcsLength(x, y string) int {
m, n := len(x), len(y)
memo := make([][]int, m+1)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
return lcsLengthMemo(x, y, m, n, memo)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
x := "ABCBDAB"
y := "BDCAB"
fmt.Printf("The length of the LCS is: %d\n", lcsLength(x, y))
}
这个实现首先创建一个二维数组
memo
用于存储已经计算过的子问题的解。
lcsLengthMemo
函数是一个递归函数，用于计算两个字符串的最长公共子序列的长度。当递归到基本情况时，它会返回 0。如果当前子问题已经计算过，它会直接返回已经计算的结果。否则，它会计算当前子问题的解，并将其存储在备忘录中，然后返回解。
lcsLength
函数是一个包装函数，用于初始化备忘录并调用
lcsLengthMemo
函数。最后，
main
函数调用
lcsLength
函数并打印结果。
