最长重复子数组

1. 如果采用暴力解法，会出现超时；
2. 采用多维动态规划（multi dynamic programming）方便解决问题，解法直观，方便大家理解；
3. dp[i][j] = (nums1[i-1] == nums2[j-1]) ? dp[i-1][j-1]+1 : 0;
4. 多维动态规划很多类似的场景，解法基本一样。如:
5. 寻找路径的总数；
6. 路径和最小值；
7. s1和s2交错生成s3

题目描述

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

示例 1：

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

C++实现

class Solution {
public:
    int findLength(vector& nums1, vector& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if (m == 0 || n == 0) {
            return 0;
        }

        vector<vector> dp(m+1, vector(n+1, 0));

        int maxLen = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (nums1[i-1] == nums2[j-1]) ? dp[i-1][j-1]+1 : 0;
                maxLen = max(maxLen, dp[i][j]);
            }
        }

        return maxLen;
    }
};

golang实现

func findLength(nums1 []int, nums2 []int) int {
    // multi dynamic programming
    m, n := len(nums1), len(nums2)
    if m==0 || n==0 {
        return 0
    }

    maxLen := 0
    // initialize dp
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if nums1[i-1] == nums2[j-1] {
                dp[i][j] = dp[i-1][j-1]+1
            }
            maxLen = max(maxLen, dp[i][j])
        }
    }

    return maxLen
}