1、前言

题目描述

2、思路

子串与子序列的区别在于，子串必须要连续，而子序列不需要连续。子序列的题目很好做，如果两个字符不想等，那么求 i + 1 和 j + 1 上最大的值。

但是子串不同的是，如果两个字符不想等，那么意味着能提供的子串为0。

dp[i][j] 的计算需要保证公共子串的连续性，因此只能依赖于 dp[i-1][j-1]；
dp[i][j-1] 和 dp[i-1][j] 表示的是不同的公共子串，不具备连续性要求

定义一个状态转移方程 dp[i][j]：长度为 i 与长度为 j 的两个子数组最大长度。
如果 nums1[i] != nums2[j]，则 dp[i][j] = 0;
nums1[i] == nums2[j]，则 dp[i][j] = dp[i - 1][j - 1] + 1。

因为最大长度散落在二维表各处，所以需要在求解过程中不断迭代最大值。

3、代码

class Solution {

    public int findLength(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
            return 0;
        }

        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];

        int max = 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;
                }

                max = Math.max(max, dp[i][j]);
            }
        }

        return max;
    }
}