LeetCode 718 最长重复子数组
🟡中等 https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
类似于 [LCR095最长子序列](LCR 095 最长公共子序列.md) ， 这里有一些区别。
先尝试思考递归，和最长子序列类似，但含义却是从两个index开始的相同子数组的长度。
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int max_len = 0;
// 遍历 nums1 和 nums2 的每个位置，尝试找到从这些位置开始的最长公共子数组
for (int i = 0; i < nums1.size(); i++) {
for (int j = 0; j < nums2.size(); j++) {
max_len = max(max_len, maxLengthFrom(nums1, i, nums2, j));
}
}
return max_len;
}
private:
int maxLengthFrom(vector<int>& nums1, int i, vector<int>& nums2, int j) {
// 基本条件：如果任何一个数组越界，则无法继续
if (i >= nums1.size() || j >= nums2.size()) return 0;
// 如果当前元素相同，则递归继续查找下一个元素
if (nums1[i] == nums2[j]) {
return 1 + maxLengthFrom(nums1, i + 1, nums2, j + 1);
} else {
// 如果当前元素不同，则子数组无法延续，返回 0
return 0;
}
}
};
修改成dp， 发现每个函数调用依赖于右下的值，因此，dp更新从下往上，如果使用二维dp数组的话左右没区别。
但是观察发现只依赖于下一层的调用，因此可以优化空间。这时，上下还是从下到上，但是必须从左到右。
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<int> dp(nums2.size()+1,0);
int res = 0;
for(int row = nums1.size()-1;row>=0;row--){
for(int col = 0;col<nums2.size();col++){
if(nums1[row]==nums2[col]) dp[col] = 1+dp[col+1];
else{
dp[col] = 0;
}
res = max(res,dp[col]);
}
}
return res;
// return add_path(nums1,0,nums2,0);
}
};