给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
解法一：动态规划
代码：
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int row = A.size(),col = B.size();
vector<vector<int>> dp(row + 1,vector<int>(col+1,0));
int maximum = 0;
for(int i = row-1;i>=0;--i){
for(int j = col-1;j>=0;--j){
dp[i][j] = dp[i+1][j+1]+((A[i] == B[j])?1:0);
maximum = max(dp[i][j],maximum);
}
}
return maximum;
}
};
思路
记A[i:]为数组第i个元素到数组尾的子数组，dp[i][j]为A[i:]和B[j:]的最长公共前缀，那么所求的重复子数组就是dp[i][j]的最大值，利用递推方程
[dp(i,j)=
egin{cases}
dp(i+1,j+1)+1,A[i]=B[j] \
0,A[i]
e B[j]
end{cases}
]
dp[len(A)-1][len(B)-1]递推到dp[0][0]，再求出数组中的最大值。