7-014-(LeetCode- 718) 最长重复子数组
1. 题目
读题
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
考查点
2. 解法
思路
这道题的思路是使用动态规划来求解。动态规划是一种将复杂问题分解为子问题的方法，通过记录子问题的解，避免重复计算，从而提高效率。动态规划的关键是找到状态和状态转移方程。
在这道题中，
我们可以定义状态为dp[i][j]，表示以A[i-1]和B[j-1]结尾的最长重复子数组的长度。
状态转移方程为：
- 如果A[i-1]和B[j-1]相等，那么dp[i][j]等于dp[i-1][j-1]加一，因为我们可以将A[i-1]和B[j-1]加到前面的重复子数组中。
- 如果A[i-1]和B[j-1]不相等，那么dp[i][j]等于0，因为没有重复子数组以A[i-1]和B[j-1]结尾。
最后，我们遍历dp数组，找到最大值，就是答案。
代码逻辑
代码的逻辑可以分为以下几个步骤：
- 创建一个m+1行n+1列的二维数组dp，用来存储动态规划的状态。
- 初始化dp数组的第一行和第一列为0，表示没有重复子数组以空字符结尾。
- 遍历A和B的每个元素，根据状态转移方程更新dp数组的值。
- 遍历dp数组，找到最大值，作为答案返回。
具体来说，代码的逻辑如下：
- 定义一个变量max，用来记录最大值，初始为0。
- 定义一个变量m，用来记录A的长度。
- 定义一个变量n，用来记录B的长度。
- 创建一个m+1行n+1列的二维数组dp，用来存储动态规划的状态。
- 用双重循环遍历dp数组的每个元素，初始化为0。
- 用双重循环遍历A和B的每个元素，根据状态转移方程更新dp数组的值。具体地，如果A[i-1]和B[j-1]相等，那么dp[i][j]等于dp[i-1][j-1]加一，否则dp[i][j]等于0。同时，更新max的值，如果dp[i][j]大于max，那么将max赋值为dp[i][j]。
- 返回max作为答案。
具体实现
class Solution {
public int findLength(int[] A, int[] B) {
int m = A.length;
int n = B.length;
// dp[i][j]表示以A[i-1]和B[j-1]结尾的最长重复子数组的长度
int[][] dp = new int[m+1][n+1];
// 初始化为0
for (int i = 0; i <= m; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = 0;
}
// 状态转移
int max = 0; // 记录最大值
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 如果A[i-1]和B[j-1]相等，那么dp[i][j]等于dp[i-1][j-1]加一
if (A[i-1] == B[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
// 更新最大值
max = Math.max(max, dp[i][j]);
} else {
// 否则，dp[i][j]等于0，表示没有重复子数组以A[i-1]和B[j-1]结尾
dp[i][j] = 0;
}
}
}
// 返回最大值
return max;
}
}
3. 总结