LeetCode-718. 最长重复子数组

题目思路

用二维数组可以记录两个字符串的所有比较情况，这样就比较好推递推公式了。

动态规划

1.确定dp数组（dp table）以及下标的含义

dp[i][j]的定义也就决定着，我们在遍历dp[i][j]的时候i 和 j都要从0开始。
这里不从0开始，会遇到一个坑

2.确定递推公式

根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。
即当A[i] 和B[j]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
依赖于前面的
在这里插入图片描述

3.dp数组如何初始化

根据dp[i][j]的定义，dp[i][0] 和dp[0][j]，相等就为1

        //初始化
        for(int i = 0;i<nums1.length;i++){
            if(nums1[i] == nums2[0]){
                dp[i][0] = 1; 
            }
        }
        //初始化
        for(int j = 0;j<nums2.length;j++){
            if(nums1[0] == nums2[j]){
                dp[0][j] = 1; 
            }
        }

4.确定遍历顺序

外层for循环遍历A，内层for循环遍历B。(顺序无所谓)
同时题目要求长度最长的子数组的长度。所以在遍历的时候顺便把dp[i][j]的最大值记录下来。

5.举例推导dp数组

拿示例1中，A: [1,2,3,2,1]，B: [3,2,1,4,7]为例，画一个dp数组的状态变化，如下：
在这里插入图片描述

代码如下：

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length][nums2.length];
        int result = 0;
        //初始化
        for(int i = 0;i<nums1.length;i++){
            if(nums1[i] == nums2[0]){
                dp[i][0] = 1; 
            }
        }
        //初始化
        for(int j = 0;j<nums2.length;j++){
            if(nums1[0] == nums2[j]){
                dp[0][j] = 1; 
            }
        }
        for(int i = 0;i<nums1.length;i++){
            for(int j = 0;j<nums2.length;j++){
                if(nums1[i] == nums2[j] && i>0 && j>0){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    
                }
                result = dp[i][j] > result ? dp[i][j]:result;
            }
        }
        return result;
    }
}

在这里插入图片描述

遇到的坑

我遇到了两个坑
第一个是低级错误，nums1[i] == nums2[j]写成了nums1[i-1] == nums2[j-1]

                if(nums1[i-1] == nums2[j-1] ){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    
                }

第二个是没判断边界值
要从i=0，j=0开始遍历，因为初始化可能为1
在这里插入图片描述

        for(int i = 0;i<nums1.length;i++){
            for(int j = 0;j<nums2.length;j++){
                if(nums1[i] == nums2[j] && i>0 && j>0){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    
                }
                result = dp[i][j] > result ? dp[i][j]:result;
            }
        }

动态规划(优化)

new int[nums1.length+1][nums2.length+1]这样就可以不用初始化了

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        int result = 0;
        for(int i = 1;i<=nums1.length;i++){
            for(int j = 1;j<=nums2.length;j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    
                }
                result = dp[i][j] > result ? dp[i][j]:result;
            }
        }
        return result;
    }
}