寻找公共子数组,类似于公共子串问题,可以定义一个二维的dp数组来记录两个数组之间的匹配情况,当 A[i] == B[j] 时,令 dp[i][j]=dp[i-1][j-1]+1 。根据该状态转移方程可以得到动态规划解法的代码如下:
class Solution {
public int findLength(int[] A
, int[] B
) {
int n
= A
.length
, m
= B
.length
;
int[][] dp
= new int[n
+ 1][m
+ 1];
int ans
= 0;
for (int i
= 1; i
<= n
; i
++) {
for (int j
= 1; j
<= m
; j
++) {
if(A
[i
-1] == B
[j
-1]){
dp
[i
][j
] = dp
[i
-1][j
-1] + 1;
ans
= Math
.max(ans
, dp
[i
][j
]);
}
}
}
return ans
;
}
}
转载请注明原文地址:https://ipadbbs.8miu.com/read-11268.html