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;
}
}
