Leetcode 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. 确定dp数组（dp table）以及下标的含义
    dp[i][j]：以下标i-1为结尾的A，和以下标j-1为结尾的B，最长重复子数组长度为dp[i][j]。（特别注意： “以下标i-1为结尾的A” 标明一定是以A[i-1]为结尾的字符串 ）

  2. 确定递推公式

    • 如果A[i-1] == B[j-1]，说明以A[i-1]和B[j-1]结尾的最长重复子数组长度为dp[i-1][j-1]+1
    • 如果A[i-1] != B[j-1]，说明以A[i-1]和B[j-1]结尾的最长重复子数组长度为0
    • 综上所述，递推公式为：dp[i][j] = A[i-1] == B[j-1] ? dp[i-1][j-1] + 1 : 0
    • 最后的结果取得是dp数组中的最大值，所以使用res记录最大值，res = Math.max(res, dp[i][j])

  3. dp数组如何初始化
    dp数组所有元素都初始化为0

  4. 确定遍历顺序
    从前往后遍历

  5. 举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        int[][] dp = new int[m + 1][n + 1];
        int res = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }
}