Golang Leetcode 718. Maximum Length of Repeated Subarray.go

版权声明：原创勿转 https://cloud.tencent.com/developer/article/1419706

思路

DP算法

dpi表示A和B共同前缀的长度

初始都是0

转移方程：dpi = dpi 1 1

code

代码语言：javascript复制

func findLength(A []int, B []int) int {
	ans := 0
	la, lb := len(A), len(B)
	dp := make([][]int, la 1)
	for k := range dp {
		dp[k] = make([]int, lb 1)
	}
	for i := la - 1; i >= 0; i-- {
		for j := lb - 1; j >= 0; j-- {
			if A[i] == B[j] {
				dp[i][j] = dp[i 1][j 1]   1
				if ans < dp[i][j] {
					ans = dp[i][j]
				}
			}
		}
	}
	return ans
}

​

code dp 算法

0 人点赞