LeetCode-718-最长重复子数组

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

示例 1:

输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释:  长度最长的公共子数组是 [3, 2, 1]。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray

class Solution { public: int findLength(vector<int>& A, vector<int>& B) { int lenA = A.size(); int lenB = B.size(); vector<vector<int>> dp(lenA,vector<int>(lenB,0)); int ans = 0; for(int i = 0;i<lenA;i++) { for(int j = 0;j<lenB;j++) { if(A[i]==B[j]) { if(i-1>=0 && j-1>=0) dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = 1; ans = std::max(ans,dp[i][j]); } } } return ans; } };

1、这道题的解法很多，可以滑动窗口，哈希+二分查找，动态规划，具体过程可以在题解里面看到。

2、我用的是动态规划，自己对动态规划相对了解一点。

3、这是一个二维动态规划题，有点像求连续子数组的升级版。

4、所以这里参照求连续子数组的思维定义连续子数组的二维动态转移方程。

dp[n][m]表示的是A数组以n为公共连续子数组结尾，B数组以m为公共连续子数组结尾时的长度。

A[i] == B[j]时，dp[i][j] = dp[i-1][j-1]+1;(注意越界问题)

ans = max(ans,dp[i][j]);

A[i] != B[j]时， dp[i][j] = 0;

5、给推荐一个大佬的公众号，动态规划讲的很好，可以看一看他对动态规划的理解，很厉害。