最长重复子数组

题目分析题解动态规划 总结

题目

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

分析

这道题属于一看就知道可以用动态规划做的那种，关键就在于怎么找出动态规划的递推公式。由于是找到两个数组的公共部分，自然而然的，我们用一个二维表的表头来存储，想递推公式时可以画一个图，更容易想，写代码时下标也更好写：

题解

动态规划

public static int findLength(int[] A, int[] B) { int i,j; int len = 0; int[][] dp = new int[A.length + 1][B.length + 1]; //建立一个二维表,横向为A数组，纵向为B数组。 for(i = 1; i <= A.length; i++){ for(j = 1; j <= B.length; j++){ // 注意下标，原数组下标和构造的二维数组下标关系 if(A[i - 1] == B[j - 1]){ //如果两个元素相等，就看左上方的匹配结果 dp[i][j] = dp[i - 1][j - 1] + 1; // 递推公式 } // 更新最长长度 len = Math.max(len,dp[i][j]); } } return len; }

总结

看到这个题，一般就能想到动态规划，找递推公式时建议画一个图，有助于理解，也便于代码的编写！