718. 最长重复子数组(dp)

 

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

示例：

输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。

提示：

• 1 <= len(A), len(B) <= 1000
• 0 <= A[i], B[i] < 100

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        int dp[n+1][m+1];
        //dp[i][j] 以i,j 为结尾的最长公共子串， 要求连续，所以不是从0到i是最长。
        //最终结果是 max(dp[i][j])
        for(int i = 0; i < n+1;++i) {
            dp[i][0] = 0;
        }
        for(int j = 0; j < m+1;++j) {
            dp[0][j] = 0;
        } 
        int res = 0;
        for(int i =1 ;i < n+1;++i) {
            for(int j = 1;j < m+1;++j) {
                if(nums1[i-1]==nums2[j-1]) {
                    dp[i][j] = 1+dp[i-1][j-1];
                } else {
                    dp[i][j] = 0; // 区别与最长子序列， s[i]!=ss[j],那么这2个子串没有公共子串
                    // [1,2,3] vs [1,2] 没有公共子串
                    // [1,2,3]以i为结尾的子串=[1,2,3][2,3]、[3]
                    // [1,2]以i为结尾的子串=[1,2][2]
                }
                res = max(res,dp[i][j]);
            }
        }
        return res;
    }
};