问题:
给定两个数组,求两个数组中最长公共子数组的长度。
Example 1: Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3, 2, 1]. Note: 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100
解法:
DP动态规划,
dp[i][j]代表到A到第i个数B到第j个数为止,连续公共子数组到长度。(且到此位,两个公共数组还在相等比较下去中)
动态转移方程:
if(A[i]==B[j]) { dp[i+1][j+1]=dp[i][j]+1; } else { dp[i+1][j+1]=0; }
边界值:dp[0][j] or dp[i][0] =0
例如,有以下两个数列,则构建到dp为以下memo数组到样子:
参考代码:
1 class Solution { 2 public: 3 //dp[i][j]=A[i]==B[j]?dp[i-1][j-1]+1:0; 4 int findLength(vector<int>& A, vector<int>& B) { 5 int n = A.size(); 6 int m = B.size(); 7 int res=0; 8 int dp[n+1][m+1]; 9 memset(dp,0,sizeof(dp)); 10 for(int i=1; i<=n; i++){ 11 for(int j=1; j<=m; j++){ 12 if(A[i-1]==B[j-1]) dp[i][j]=dp[i-1][j-1]+1; 13 else dp[i][j]=0; 14 res=max(res, dp[i][j]); 15 } 16 } 17 return res; 18 } 19 };