【leetcode】718. 最长重复子数组（maximum-length-of-repeated-subarray）（DP）[中等]

链接

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

耗时

解题：14 min 题解：22 min

题意

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

思路

最长公共子序列。 二维DP，dp[i][j]，[i] 指数组 A 对应的元素A[i]，[j] 指数组 B 对应的元素B[j]，dp[i][j] 是 A[0~i] 和 B[0~j] 中包含 A[i]、B[j] 的最长公共子序列长度，那么最终的最长公共子序列即是 dp[i][j] 中的最大值。 状态转移方程： $$dp[i][j]=\{\begin{array}{l}dp[i-1][j-1]+1(A[i]==B[j])\\ 0(其它)\end{array}$$ 因为 dp[i][j] 的值从 dp[i-1][j-1] 转移得到，所以 dp[i][0] 和 dp[0][j] 需要空出来。

AC代码

class Solution { public: int findLength(vector<int>& A, vector<int>& B) { int dp[1100][1100]; memset(dp, 0, sizeof(dp)); int max_len = 0; for(int i = 1; i <= A.size(); ++i) { for(int j = 1; j <= B.size(); ++j) { if(A[i-1] == B[j-1]) { dp[i][j] = dp[i-1][j-1]+1; if(dp[i][j] > max_len) max_len = dp[i][j]; } } } return max_len; } };