最长公共子序列（数组，动态规划）

GitHub：github.com/bllon/Data-structure-an...
题目：

最长公共子序列
求给定的两个数组的最长公共子序列长度
例如 arr1 = [1,2,4,6,9,13], arr2 = [1,3,4,6,9,15]
那么最长公共子序列长度为4, (1,4,6,9)

解法: 来自百度百科
动态规划的一个计算两个序列的最长公共子序列的方法如下： [1]
以两个序列 X、Y 为例子：
设有二维数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有：
f[1][1] = same(1,1);
f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]};
其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”，否则为“0”。
此时，二维数组中最大的数便是 X 和 Y 的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。
该算法的空间、时间复杂度均为O(n^2)，经过优化后，空间复杂度可为O(n)。

代码：

package main

import "fmt"

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func same(a, b int) int {
    if a == b {
        return 1
    }
    return 0
}

func LCSL(arr1 []int, arr2 []int) int {
    len1, len2 := len(arr1), len(arr2)
    if len1 == 0 || len2 == 0 {
        return 0
    }

    //dp数组
    var dp [][]int //dp[i][j]代表arr1[i]和arr2[j]的位置之前最长公共子序列长度
    dp = make([][]int, len1+1)
    for i := 0; i <= len1; i++ {
        dp[i] = make([]int, len2+1)
    }

    for i := 1; i <= len1; i++ {
        for j := 1; j <= len2; j++ {
            if arr1[i-1] == arr2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            }
        }
    }

    return dp[len1][len2]
}

func main() {
    fmt.Println(LCSL([]int{1, 2, 4, 6, 9, 13, 15}, []int{1, 3, 4, 6, 9, 15}))
    return
}

结果：

5

本作品采用《CC 协议》，转载必须注明作者和本文链接