【LeetCode】每日一题2021/12/15

• 思路
  想到一个O(n³)时间复杂度的双指针方法，想找相等，然后再依次向后移动，肯定不好。
  重叠子问题想到动态规划，但是这道题两个数组，我们怎么去定义呢？
  参考题解
  
  
  

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        // 初始化，dp[i][0], dp[0][j]默认已经初始化为0
        int max = 0;
        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (max < dp[i][j]) {
                    max = dp[i][j];
                }
            }
        }
        return max;
    }
}