718. 最长重复子数组 经典
组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 1:
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。
说明:
- 1 <= len(A), len(B) <= 1000
- 0 <= A[i], B[i] < 100
3 2 1 4 7
1 0 0 1 0 0
2 0 1 0 0 0
3 1 0 0 0 0
2 0 2 0 0 0
1 0 0 3 0 0
dpi代表以A[i-1]与B[j-1]结尾的公共字串的长度,公共字串必须以A[i-1]，B[j-1]结束，即当A[i-1] == B[j-1]时，dpi = dpi-1 + 1; 当A[i-1] != B[j-1]时，以A[i-1]和B[j-1]结尾的公共字串长度为0,dpi = 0。输出最大的公共字串的长度即为最长重复字串。 打个表会更直观一点
第一版，最大公共子序列和子数组是不同的，DP解法
执行用时 :260 ms, 在所有 cpp 提交中击败了66.71%的用户
内存消耗 :106.1 MB, 在所有 cpp 提交中击败了58.93%的用户
intfindLength(vector<int>&A, vector<int>&B) {
intlen1=A.size(), len2=B.size(),maxNum=0;
vector<vector<int>>dp(len1 , vector<int>(len2 , 0));
for (inti=0; i<len1; ++i) {
for (intj=0; j<len2; ++j) {
if (i==0||j==0) {
dp[i][j] =A[i] ==B[j] ?1 : 0;
}
else if (A[i] ==B[j])
{
dp[i][j] =dp[i-1][j-1] +1;
maxNum=max(maxNum, dp[i][j]);
}
else
dp[i][j]=0;
}
}
returnmaxNum;
}
第二版，这是最大公共子序列的解法
3 2 1 4 71 0 0 1 1 12 0 1 1 1 13 1 1 1 1 12 1 2 2 2 21 1 2 3 3 3
intfindLength(vector<int>&A, vector<int>&B) {
intlen1=A.size(), len2=B.size();
vector<vector<int>>dp(len1 , vector<int>(len2 , 0));
for (inti=0; i<len1; ++i) {
if (A[i] ==B[0]) {
while (i<len1)
dp[i++][0] =1;
}
}
for (intj=0; j<len2; ++j) {
if (B[j] ==A[0]) {
while (j<len2)
dp[0][j++] =1;
}
}
for (inti=1; i<len1; ++i) {
for (intj=1; j<len2; ++j) {
if (A[i] ==B[j])
dp[i][j] =dp[i-1][j-1] +1;
else
dp[i][j] =max(dp[i-1][j],dp[i][j-1]);
}
}
returndp[len1-1][len2-1];
}
