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 <= nums1[i], nums2[i] <= 100

算法思路：

考虑动态规划，dp[i][j] 表示字符串 text1中子串 [0, i - 1] 与字符串 text2 中子串 [0, j - 1] 的最长公共子序列的长度。递推公式如下：

• 对于 i，j（i>=1,j>=1)：
  • 如果 text1[i] == text2[j]，则 dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
  • 否则，dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
• i==0,j==0时，即 dp[0][0]初始化为 0 。

代码实现：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length(), len2 = text2.length();
        // dp[i][j]: 字符串 text1中子串 [0, i - 1] 与字符串 text2 中子串 [0, j - 1] 的最⻓公共⼦序列的长度
        int[][] dp = new int[len1 + 1][len2 + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                // 找到了⼀个公共元素，和其前面的 dp[i - 1][j - 1] + 1 取较大值
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                } else {
                    //不相同则取 dp[i][j - 1], dp[i - 1][j] 中较大值
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[len1][len2];
    }
}

Q.E.D.