718.最长重复子数组

题目描述

给你两个整数数组nums1和nums2，返回两个数组中的公共的、长度最长的子数组长度

示例1：

输入：nums1 = [1,2,3,2,1]，nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是[3,2,1]。

示例2：

输入：nums1 = [0,0,0,0,0]，nums2 = [0,0,0,0,0]
输出：5

提示：

• 1<=nums1.length, nums2.length<=1000
• 0<=nums[i],nums2[i]<=100

解题思路

1. 确定dp数组的含义
dp[i][j]：以下标i-1为结尾的的nums1和以下标j-1为结尾的nums2的最长重复子数组的长度为dp[i][j]
2. 递推公式
if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1
3. dp数组初始化
dp数组第一行第一列为无意义状态，故初始化为0，可以把整个dp数组都初始化为0
4. 遍历顺序
dp[i][j]的状态由dp[i-1][j-1]的状态推导出来，因此遍历顺序为从前往后
5. 打印dp数组

代码实现

• 核心模式

class Solution{
public:
    int findLengthOfLCIS(const vector<int>& nums1, const vector<int>& nums2){
        // initialize the DP array
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));

        int length = 0;
        // traversal 
        for (int i = 1; i <= nums1.size(); i++){
            for (int j = 1; j <= nums2.size(); j++){
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > length) length = dp[i][j];
            }
        }

        return length;
    }
};

• ACM模式
dynamicPro.h

#include <iostream>
#include "dynamicPro.h"

class Solution{
public:
    int findLengthOfLCIS(const vector<int>& nums1, const vector<int>& nums2){
        // initialize the DP array
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));

        int length = 0;
        // traversal 
        for (int i = 1; i <= nums1.size(); i++){
            for (int j = 1; j <= nums2.size(); j++){
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > length) length = dp[i][j];
            }
        }

        print2DVector(dp);

        return length;
    }
};

int main(){
    vector<int> case11 = {1, 2, 3, 2, 1};
    vector<int> case12 = {3, 2, 1, 4, 7};
    vector<int> case21 = {0, 0, 0, 0, 0};
    vector<int> case22 = {0, 0, 0, 0, 0};

    Solution solution;
    cout << "Result1's DP array = " << solution.findLengthOfLCIS(case11, case12) << endl;
    cout << "Result2's DP array = " << solution.findLengthOfLCIS(case21, case22) << endl;

    return 0;
}

• 输出

Result1's DP array = [[0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 2, 0, 0, 0], [0, 0, 0, 3, 0, 0]]
3
Result2's DP array = [[0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 2, 2, 2, 2], [0, 1, 2, 3, 3, 3], [0, 1, 2, 3, 4, 4], [0, 1, 2, 3, 4, 5]]
5